^Algorithms and Data Structures^

FAQ, Algorithms and Data Structures
NB. For matters relating specifically to the programming language C, see [here].
Question: Why should I learn about algorithms and data structures?
Answer 1: Here is one possible reason that came in some recent email from a Monash Comp' Sci' graduate now working overseas:
". . . It's a pity that [some university's] graduates don't know anything about recursion, hashing, B-Tree, quick sort, binary search trees, ..., etc. anymore. I find my services in high demand for just being able to think straight! . . ."
Answer 2: "Oh yes, I had to use that [shortest-paths algorithm] in a recent job." -- ex cse2304 student.
Answer 3: "I needed to use an [AVL-tree] during a summer vacation project" --3rd-year rep..


Question: Did the content or difficulty of the subject increase when it changed from 4 points (CSC2040) to 6 points (CSE2304)?
Answer: No. Only the points-value changed: The difficulty of CSC2040 (4pts to 1998) and CSE2304 (6pts from 1999 onwards) are approximately the same although the content changed very slightly - red-black trees were replaced by AVL trees, for example.


Question: How many candidates fail the subject?
Answer: This varies from year to year (after all, enrolments and cut-offs have also varied recently). There is no "set percentage" that must pass or fail. Some figures for past years are available on the subject [home page]. For example, [2002] was a v. good year with about 32% High Distinctions (HD) and 19% Distinctions (D) but the [2004] results were poorer despite the 2002 and 2004 papers being rather similar. The [2005] results were good with 15% HD and 24% D. In [2006] there were 18% HD and 15% D. By coincidence, 14% with full assessment failed in 2005 and in 2006.


Question: If I am repeating the subject, can I use my practical mark from the previous year, thus only taking the exam component this year?
Answer: No. You must sit and pass all of the assessment for the subject in the one semester. You cannot take your practical mark from the previous year, nor your exam mark from the previous year, nor your best exam-question of the previous year's paper etc..
However if you have previously completed all the assessment but failed the unit, two or more times, then you may apply to count the arithmetic mean (rounded, e.g. 17.4/30->17/30, 17.5/30->18/30) of your practical marks from all your previous attempts at the practical work. You must apply on or before the Thursday of week two of the unit at the latest and you must give good reasons why it is necessary. If this is allowed, and it might not be, you must still attend the tutorials and you are very strongly advised to practice your programming skills, a lot. NB. You cannot then still do the practical work and take the higher result.


Question: How should I revise for the exam?
Answer: Practising past [exam papers] and tutorial questions (there are notes on some of the [past tutorials]) is a good start. You should also make sure that you understand (rather than just memorize) the various data-structures, algorithms, strategies, and analysis and proof methods for algorithms and data structures. (Also check up on your [Prerequisite Knowledge].)


Question: Must I remember the best-, average- and worst-case time- and space-complexities of Quicksort, Heap sort, ..., Prim's algorithm, ... etc. ... for the exam?
Answer 1: Yes.
Answer 2: No. It is better to learn the general methods of how to calculate these complexities instead.


Question: Must I learn the code for [some algorithm] by heart?
Answer 1: Yes.
Answer 2: No. A better strategy is to remember the intuitive idea behind an algorithm and become a good enough, and confident enough, programmer to be able to turn that idea into correct code in your (chosen | required) programming language.


Question: Why are the notes in HTML?
Answer: HTML has the following advantages: (i) It reformats automatically to different window sizes, often doing a reasonable job from as narrow as WIDTH 500 and upwards (My desk top goes up to 3200 wide, and technology will gives us both narrower screens on PDAs etc. and wider screens with e-paper etc.), and with different FONT sizes, e.g. +1 or +2 as often projected in R1 (Resources permitting, the school does a standard print run if you want a paper copy.), (ii) Javascript algorithm demonstrations can run within a page ([e.g.] see slide 2) which is useful in lectures, (iii) hyper links can be given to other material (some other file formats can now do this too), (iv) it is non-proprietary, (v) browsers for the file format are standard on "all" operating systems, (vi) it is a "light" file format, the files are small (Less load on the server, good for slow connections. Ever noticed how broad-band has not made things much faster?) and (vii) SHTML server-side "includes" are very useful for management purposes (it matters to staff!).


Question: How do I compile a C program that is split across more than one `.h' and/or `.c' files?
Answer: In this subject, the typical such program, provided that it exists in a directory of its own, can usually be compiled by changing,  cd,  to the directory and running the compiler thus: `gcc *.c'. If the program is particularly large, i.e. many files, you might conceivably need to use `make' and make-files (try `man make'), but this is rarely if ever the case for this subject. (It is however a useful computing skill to learn.)


Question: Is there a bug in fscanf()?
Answer: No. All examples of students' programs crashing in fscanf are due to student programming errors that have corrupted memory, e.g. writing off the end of an array (e.g. due to carelessly dropping the use of a sentinel in insertion sort). Some time later fscanf allocates some memory, but the necessary system information has been corrupted. The program might "run" for a time on a different system and crash at some other location, or even not crash, but it would eventually misbehave in some other way.

L. Allison, School of Computer Science and Software Engineering, Faculty of Information Technology, Monash University, Australia 3800. (Was Dept. Computer Science, Monash University.)