FIT2009 - Data structures and algorithms - 2017

6 points, SCA Band 2, 0.125 EFTSL

Undergraduate - Unit

Refer to the specific census and withdrawal dates for the semester(s) in which this unit is offered.

Faculty

Information Technology

Unit guides

Offered

South Africa

  • Second semester 2017 (Day)

Synopsis

Algorithm analysis. Application and implementation of some common data structures: stacks, queues, lists, priority queues, tables, sets and collections. Data representations including: arrays, linked lists, heaps, trees (including balanced trees) and hashing. Design of application programs making use of common data structures. Design and implementation of new data structures. Study of advanced algorithms in areas such as: graph theory, pattern searching and data compression. Access to the University's computer systems through an Internet service provider is compulsory for off-campus students.

Outcomes

At the completion of this unit, students should be able to:

  1. analyse simple algorithms to work out an order of magnitude estimate of running time and space;
  2. describe and implement the most common data structures: stacks, queues, lists, priority queues, tables, sets, collections using various common data representations: arrays, linked lists, heaps, trees (including balanced trees), hashing;
  3. evaluate which implementation would be most appropriate for a given data structure and application;
  4. apply the same principles used in implementing the common data structures to implement other data structures and design and implement new data structures;
  5. describe more advanced algorithms in areas such as: graph theory (shortest path etc), pattern searching, data compression (precise selection of advanced algorithms will vary from year to year);
  6. design new algorithms to solve new problems.

Assessment

Examination (2 hours): 60%; In-semester assessment: 40%

Workload requirements

Minimum total expected workload equals 12 hours per week comprising:

  1. Contact hours for on-campus students:
    • One 2-hour lecture
    • One 2-hour laboratory
  2. Study schedule for off-campus students:
    • Off-campus students generally do not attend lecture and tutorial/laboratory sessions, however should plan to spend equivalent time working through the relevant resources and participating in discussion groups each week.
  3. Additional requirements (all students):
    • a minimum of 8 hours of independent study in some weeks for completing lab and project work, private study and revision.

See also Unit timetable information

Chief examiner(s)

This unit applies to the following area(s) of study

Prerequisites

FIT1007 or GCO1812 or GCO9808 or FIT2034

Prohibitions

FIT2004, FIT2071, FIT9015, GCO2817, GCO3512, GCO9807

Additional information on this unit is available from the faculty at: