COMP10002 Foundations of Algorithms

School of Computing and Information Systems

Semester 2, 2019 Assignment 1

Learning Outcomes

In this project you will demonstrate your understanding of arrays, strings, and functions. You may also use typedefs and structs if you wish (see Chapter 8) – and will probably find the program easier to assemble if you do – but you are not required to use them in order to obtain full marks. You should not make any use of malloc() (Chapter 10) or file operations (Chapter 11) in this project.

Text Formatting

We all want our written work to look good. But when preparing text with a text editor it is annoying to (for example) try and adjust the line-lengths in a document every time we alter it, or if we decide that the text width needs to be narrower. So we use approaches that let us describe the layout of documents, and apply a compiler-like tool to generate the exact formatting that we are after. For example, this document (and most other things you will see in this subject, including the textbook) was prepared using a typesetting tool called LATEX, and you can see the source code for it linked from the LMS/FAQ page. Use of LATEX allows math expressions like (plus far more complex expressions too) to be elegantly presented, and allows careful and consistent formatting to be applied throughout long documents. A WYSIWYG[1] (or more usually, WYCSIAYCG) tool like Word might be employed to write a one-page reference letter, but for technical work academics in the maths, physics, and computing sciences almost always prefer LATEX. (It was originally invented by one of the most famous computer scientists of all, Stanford University’s Donald E. Knuth, and now has a world-wide community of developers and language extenders.) Similarly, html tags in conjunction with a style sheet file describe how the contents of a web page are to be rendered and presented.

In this assignment we are going to journey back to the 1970s, and implement a simple text formatting tool based entirely on fixed-width terminal fonts and character-based output. The formatting “commands” will be indicated by input lines that start with a period, “.”, with the command indicated by the letter in the next character position. For example, the characters “.p” in the first two positions of a line are (in this simple language) the signal to start a new paragraph in the output.

Stage 1 – Filling Lines (8/15 marks)

The first version of your program should:

  • read text input from stdin (you may assume that input lines will be at most 999 characters long); completely discard the content of all lines that commence with a period character;
  • replace all instances of (multiple) whitespace characters (blanks, tabs, newlines) by single blanks;
  • re-insert newline characters in a greedy line-by-line manner, so that each output line emitted is as long as possible, but not longer than 50 characters;
  • with the exception that if there is an input token/word that is greater than 50 characters, it goes on an output line by itself, and that line can be greater than 50 characters long.

The lines in the output should be arranged so that the left margin has a default of 4 initial blanks, and hence that the first non-blank character in each line is in column 4 (counting the columns from zero), and the last character in any line (except as noted in connection with very long tokens) is never beyond column 53 in each output line. For example, if the file test0.txt contains

one two three four five six seven eight

nine

ten eleven twelve thirteen fourteen

fifteen sixteen

seventeen

eighteen nineteen twenty.

.b

Enough of the numbers already, what about:

101, 102, 103, 104, 105, 106, 107, 108, and 109?

Plus 110, 111, 112, 113, 114 and all of 115 116 117 118 and 119.

the output should be

0----5---10---15---20---25---30---35---40---45---50---55---60 mac: ass1-soln < test0.txt one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty. Enough of the numbers already, what about: 101, 102, 103, 104, 105, 106, 107, 108, and 109? Plus 110, 111, 112, 113, 114 and all of 115 116 117 118 and 119. mac: 0----5---10---15---20---25---30---35---40---45---50---55---60

where the two “rulers” are not part of the output and are provided here to help you count character positions. (But, hint hint, they were part of the output while the sample solution was being debugged.) See the FAQ page linked from the LMS for more example input files and the output that is expected. Note that the values 4 and 50 should be held in variables assigned via initial #define starting points – you will need to be able to change their values in Stage 2.

The getword() function that was discussed in class may look like a tempting starting point. But you need to be able to examine the first character of each line without necessarily consuming it, and so a main loop that reads and processes lines is probably a better bet. You can then break that line up into tokens as required. You should also pay close attention to the item on the FAQ page that discusses the issues that may arise in connection with newline characters.

Note also that while it is possible to achieve the limited functionality required in this stage with a program that is little more than a “while(getchar())” loop, you will only receive 8/8 for a Stage 1 submission if your program shows that you have planned it in a way that allows the functionality required for Stage 2 and Stage 3 to be added without needing to completely rewrite it.

Stage 2 – Processing Commands (13/15 marks)

Once you have the Stage 1 program operational (and submitted, so that it is “on the record”), extend your program so that it recognizes and acts upon the following commands, where the “.” that indicates a formatting command always appears in the first position of an input line, straight after a newline character:

  • .b – break the current line, so that the next input token starts at the beginning of the next line;
  • .p – leave a blank line and start a new paragraph without altering the margins, with the next input token starting the new paragraph;
  • .l nn – alter the left margin from its current value (default initial value of 4) to the new value nn, and start a new paragraph;
  • .w nn – alter the width of each line from its current value (default initial value of 50) to the new value nn, and start a new paragraph.

There are further examples showing the required output linked from the LMS.

Stage 3 – Adding Structure (15/15 marks)

Now add two further commands:

  • .c – take the remaining contents of this line and center them within the current output width. If the remaining contents cannot fit within the current output width, then it should be placed so that it starts at the left margin and overflows beyond the current width. When there is an odd number of spaces to be assigned, the rounded-down half should be at the beginning of the line, and the rounded-up half at the end of the line.
  • .h nn – take the remainder of the contents of this line and use them as a section heading at the level indicated by nn. The Section/subsection/subsubsection number should be printed, and then the complete heading on a single line, even if it is longer that the current width. Headings at level nn reset the numbering for headings level nn + 1,nn + 2, and so on; and (to avoid non-computing people from being confused) all headings start their counting from one. At most five levels of headings may occur, counting from nn = 1 (the top-level heading) to nn = 5. All headings are always preceded and followed by a paragraph boundary, and level-1 headings are also preceded by a full-width line of “-” characters.

Again, see the FAQ page for linked examples of input and output combinations.

Beyond the Scope of the Project

Bored? Fidgetty? Lost interest in facebook? How about:

  • .i – make an item in a bulleted list, just like this sentence is part of a bulleted list generated by LATE Use a “o” as the “bullet” character, and indent the left margin by three characters and reduce the width by three spaces, until then next “.p” or “.b” command occurs, which ends the bulleted list. (But please dont submit any such programs for assessment, even if you get them working prior to the submission deadline.)
  • Or, if you want to do something even more rewarding, find an on-line LATEX tutorial, install one of the many free LATEX packages, and teach yourself how to make professional-looking documents.

(And you’ll never have to fight with Word again...)

General tips...

You will probably find it helpful to include a DEBUG mode in your program that prints out intermediate data and variable values. Use #if (DEBUG) and #endif around such blocks of code, and then #define DEBUG 1 or #define DEBUG 0 at the top. Turn off the debug mode when making your final submission, but leave the debug code in place. The FAQ page has more information about this.

The sequence of stages described in this handout is deliberate – it represents a sensible path though to the final program. You can, of course, ignore the advice and try and write final program in a single effort, without developing it incrementally and testing it in phases. You might even get away with it, this time and at this somewhat limited scale, and develop a program that works. But in general, one of the key things that makes some people better at programming than others is the ability to see a design path through simple programs, to more comprehensive programs, to final programs, that keeps the complexity under control at all times. That is one of the skills this is subject is intended to teach you. And if you submit each of the stages as you complete it, you’ll know that you are accumulating evidence should you need to demonstrate your progress in the event of a special consideration application becoming necessary.

The boring stuff...

This project is worth 15% of your final mark. A rubric explaining the marking expectations is provided on the FAQ page. You need to submit your program for assessment; detailed instructions on how to do that will be posted on the FAQ page once submissions are opened. Submission will not be done via the LMS; instead you will need to log in to a Unix server and submit your files to a software system known as submit. You can (and should) use submit both early and often – to get used to the way it works, and also to check that your program compiles correctly on our test system, which has some different characteristics to the lab machines. Failure to follow this simple advice is highly likely to result in tears. Only the last submission that you make before the deadline will be marked. Marks and a sample solution will be available on the LMS before Tuesday 8 October.

Academic Honesty: You may discuss your work during your workshop, and with others in the class, but what gets typed into your program must be individual work, not copied from anyone else. So, do not give hard copy or soft copy of your work to anyone else; do not “lend” your “Uni backup” memory stick to others for any reason at all; and do not ask others to give you their programs “just so that I can take a look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions in “compare every pair” mode. Students whose programs are so identified will either lose marks through the marking rubric, or will be referred to the Student Center for possible disciplinary action without further warning. This message is the warning. See https://academicintegrity.unimelb.edu.au for more information. Note also that solicitation of solutions via posts to online forums or marketplaces, whether or not there is payment involved, is also Academic Misconduct. In the past students have had their enrollment terminated for such behavior.

The FAQ page contains wording for an Authorship Declaration that you **must** include as a comment at the top of your submitted program. A significant fraction of the available marks will be deducted if you do not do so.

And remember, algorithms are fun!

Diploma Universities Assignments

Laureate International Universities Assignment

Holmes Institute Assignment

Tafe NSW

Yes College Australia

ACC508 Informatics and Financial Applications Task 2 T2, 2019

ACC512 Accounting

ACC520 Legal Regulation of Business Structures Semester 2, 2019

ACCT20074 Contemporary Accounting Theory Term 2 Assessment 3

AERO2463 Computational Engineering Analysis : Assignment 4

B01DBFN212 Database Fundamentals Assessment 1

BE01106 - Business Statistics Assignment

BFA301 Advanced Financial Accounting

BFA504 Accounting Systems Assessment 3

BSB61015 Advanced Diploma of Leadership and Management

BSBADV602 Develop an Advertising Campaign

BSBCOM603 Plan and establish compliance management systems case study

BSBCOM603 Plan and establish compliance management systems Assessment Task 1

BSBCOM603 Plan and establish compliance management systems Assessment Task 2

BSBCOM603 Plan and establish compliance management systems Assessment Task 3

BSBFIM501 Manage Budgets And Financial Plans Assessment Task 1

BSBHRM602 Manage Human Resources Strategic Planning

BSBINM601 Manage Knowledge and Information

BSBWOR501 Assessment Task 3 Plan Personal Development Plan Project

BSBMGT517 Manage Operational Plan

BSBWHS521 Ensure a Safe Workplace For a Work Area

BSBWRK510 Manage employee relations

BUSS1030 Accounting, Business and Society

CAB202 Microprocessors and Digital Systems Assignment Help

CHC40213 Certificate IV in Education Support

CHCAGE001 Facilitate the empowerment of older people

CHCAGE005 Provide support to people living with dementia

CHCCCS023 Support independence and wellbeing

CHCCCS025 Support relationships with carers and families

CHCCOM005 Communicate and CHCLEG001 Work Legally Ethically

CHCDIS002 Follow established person-centred behaviour supports

CHCECE019 Early Childhood Education and Care

CHCHCS001 Provide home and community support services

COMP10002 Foundations of Algorithms

COMP90038 Algorithms and Complexity

COSC2633/2637 Big Data Processing

COSC473 Introduction to Computer Systems

CPCCBC5011A Manage Environmental Management Practices And Processes In Building And Construction

CPCCBC5018A Apply structural Principles Medium rise Construction

CSE3OSA Assignment 2019

ELEC242 2019 Session 2

ENN543 Data Analytics and Optimisation

ENN543 Data Analytics and Optimisation Semester 2, 2019

FINM202 Financial Management Assessment 3 Group Report

Forensic Investigation Case Assignment ECU University

HA2042 Accounting Information Systems T2 2019

HC1010 Holmes Institute Accounting For Business

HC2112 Service Marketing and Relationship Marketing Individual Assignment T2 2019

HC2121 Comparative Business Ethics & Social Responsibility T2 2019

HI5002 Holmes Institute Finance for Business

HI5003 Economics for Business Trimester 2 2019

HI5004 Marketing Management T1 2020 Individual Report

HI5004 Marketing Management T1 2020 Group Report

HI5004 Holmes Institute Marketing Management

HI5014 International Business across Borders Assignment 1

HI5014 International Business across Borders

HI5017 Managerial Accounting T2 2019

HI5017 Managerial Accounting T1 2019

HI5019 Tutorial Questions 1

HI5019 Strategic Information Systems for Business and Enterprise T1 2020

HI5019 Holmes Institute Strategic Information Systems T2

HI5019 T2 2019

HI5019 T1 2019

HI5020 Corporate Accounting T3 2019

HI5020 Corporate Accounting T2 2019

HI6005: Management and Organisations in a Global Environment

HI6006 Tutorial questions

HI6006 Competitive Strategy Individual T1 2020

HI6006 Holmes Institute Competitive Strategy

HI6006 Competitive Strategy T3 2019

HI6007 Statistics for business decisions

HI6007 Assessment 2 T1 2020

HI6007 T1 2019

HI6008 T2 2019

HI6008 Holmes Institute Research Project

HI6025 Accounting Theory and Current Issues

HI6026 Audit, Assurance and Compliance Assignment Help

HI6026 Audit, Assurance and Compliance

HI6027 business and corporate law tutorial Assignment T1 2021

HI6027 Business and Corporate Law T3 2019

HI6027 Business and Corporate Law T2 2019

HI6028 Taxation Theory, Practice and Law T2 2021

Hi6028 taxation theory, practice and law Final Assessment t1 2021

HI6028 Taxation Theory, Practice and Law T2 2019

HI6028 Taxation Theory T1 2019

HI6028 Taxation Law Holmes

HLTAAP001 Recognise healthy body systems

HLTWHS002 Follow safe practices for direct client care

HOTL5003 Hotel Property and Operations

HPS771 - Research Methods in Psychology A

HS2021 Database Design

ICTICT307 Customise packaged software applications for clients

IFN619 Data Analytics for Strategic Decision Makers

INF80028 Business Process Management Swinburne University

ISY2005 Case Assignment Assessment 2

ISYS326: Information Systems Security Assignment 2, Semester 2, 2019

ITAP3010 Developing Data Access Solutions Project

ITECH1103- Big Data and Analytics – Lab 3 – Working with Data Items

ITECH1103- Big Data and Analytics Assignment Semester 1, 2020

ITECH 5500 Professional Research and Communication

Kent Institute Australia Assignment

MA5830 Data Visualisation Assignment 2

MGMT7020 Project Management Plan

Mgt 301 Assessment 3

MGT215 Project Management Individual Assignment

MIS102 Data and Networking Assignment Help

MITS4002 Object Oriented Software Development

MITS5002 Software Engineering Methodology

MKT01760 Tourism Planning Environments Assessment 4

MKT01760 Tourism Planning Environments

MKT01906 International Tourism Systems

MKT5000 Marketing Management S2 2019

MNG03236 Report Writing SCU

MRE5003 Industrial Techniques In Maintenance Management Assignment 4

MRE5003 Industrial Techniques In Maintenance Management Assignment 3

MRE5003 Industrial Techniques In Maintenance Management

Network Security and Mitigation Strategies Answers

NIT2213 Software Engineering Assignment

NSB231 Integrated Nursing Practice Assessment Task 1

Science Literacy Assessment 4

SIT323 Practical Software Development T 2, 2019

SIT718 Using aggregation functions for data analysis

SITXCOM002 Show Social and Cultural Sensitivity

TLIL5055 Manage a supply chain

TLIR5014 Manage Suppliers

USQ ACC5502 Accounting and Financial Management

UTS: 48370 Road and Transport Engineering Assessment 2

CHCAGE001 Facilitate the empowerment of older people

CHCAGE005 Provide support to people living with dementia

CHCCCS011 Meet personal support needs

CHCCCS015 Provide Individualised Support

CHCCCS023 Support independence and wellbeing

CHCCCS025 Support relationships with carers and families

CHCCOM005 Communicate and work in health or community services

CHCDIS001 Contribute to ongoing skills development

CHCDIS002 Follow established person-centred behaviour supports

CHCDIS003 Support community participation and social inclusion

CHCDIS005 Develop and provide person-centred service responses

CHCDIS007 Facilitate the empowerment of people with disability

CHCDIS008 Facilitate community participation and social inclusion

CHCDIS009 Facilitate ongoing skills development

CHCDIS010 Provide person-centred services

CHCDIV001 Work with diverse people

CHCHCS001 Provide home and community support services

CHCLEG001 Work legally and ethically

CHCLEG003 Manage legal and ethical compliance

HLTAAP001 Recognise healthy body systems

HLTAID003 Provide First Aid

HLTHPS007 Administer and monitor medications

HLTWHS002 Follow safe work practices for direct client care

Assignment 2 Introduction to Digital Forensics

MGT603 Systems Thinking Assessment 1

MGT603 Systems Thinking Assessment 2

Hi5017 Managerial Accounting T1 2021

HI6028 Taxation Theory, Practice and Law T1 2021

OODP101 Assessment Task 3 T1 2021

ITNE2003R Network Configuration and Management Project

Australia Universities

ACT

Australian Catholic University

Australian National University

Bond University

Central Queensland University

Charles Darwin University

Charles Sturt University

Curtin University of Technology

Deakin University

Edith Cowan University

Flinders University

Griffith University

Holmes Institute

James Cook University

La Trobe University

Macquarie University

Monash University

Murdoch University

Queensland University of Technology

RMIT University

Southern Cross University

Swinburne University of Technology

University of Adelaide

University of Ballarat

University of Canberra

University of Melbourne

University of Newcastle

University of New England

University of New South Wales

University of Notre Dame Australia

University of Queensland

University of South Australia

University of Southern Queensland

University of Sydney

University of Tasmania

University of Technology Sydney

University of the Sunshine Coast

University of Western Australia

University of Wollongong

Victoria University

Western Sydney University

Year 11 - 12 Certification Assignment

Australian Capital Territory Year 12 Certificate

HSC - Higher School Certificate

NTCE - Northern Territory Certificate of Education

QCE - Queensland Certificate of Education

SACE - South Australian Certificate of Education

TCE - Tasmanian Certificate of Education

VCE - Victorian Certificate of Education

WACE - Western Australia Certificate of Education