Programming and Data Structures: Spring 2013

Course Information

• Instructor: Deepayan Sarkar <deepayan.sarkar@gmail.com>

References

• The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie.
• Introduction To Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Grading (tentative)

• Mid-term Exam: 30%
• End-term Exam: 50%
• Assignments: 20%

Code examples

• January 24: sort.c (implementation of merge sort). To compile on Linux, use

  $ gcc -o sort sort.c -lm

• January 28: sort.c (updated to apply on generated data with seed values read at runtime using scanf()).
• January 29: sort.c (pointers, dynamic allocation, random numbers, and timing). To compile, use

  $ gcc -o sort sort.c -lm -lrt

• February 4: ascii.c (characters, strings, and command-line arguments).
• February 5: insertion_sort.c, insertion_sort.h, merge_sort.c, merge_sort.c, sort_file.c (compiling separate files, header files, and reading from files). To compile, use

  $ gcc -o sort_file merge_sort.c insertion_sort.c sort_file.c -lm

• February 7: time_sort.c, Makefile (make file).
• March 7: struct.c, heap.c.
• March 12: insertion_sort.c, insertion_sort.h, merge_sort.c, merge_sort.h, rsort.c, Makefile, rsort.R,
• March 19: llist.c, llist.h (linked lists).
• April 1: hash_table.c, hash_table.h (hash tables).
• April 9: bst_height.c, bst_height.h, bst_wcount.c, bst_wcount.h (binary search trees).

Assignments

• Assignment 1 (due 4 February): Implement the insertion sort algorithm presented in class in C (including a run-time analysis as done with merge sort).

  Your solution should consist of a single file named according to the pattern FirstnameLastname.c, which should be emailed to me. I will compile it with gcc -lm -lrt. If your file needs different compilation directives, mention that in your email.

• Assignment 2 (due 14 February): Modify the insertion sort and merge sort algorithms so that given an input array A of size n, they compute a permutation of {0, 1, 2, ..., n-1} that sorts A (i.e., A[i[0]], A[i[1]], ... should be sorted, where i is an integer array containing the computed permutation). Submit hard copies of the algorithms you have written.

  In addition, implement your algorithm as C functions called insertion_order and merge_order. They should have the following signatures:

  void insertion_order(int n, double *A, int *i);
  void merge_order(int n, double *A, int *i);

  where n is the length of the input array, A is a pointer to the input array, and i is a pointer to the array that is to hold the computed permutation. The memory required for x and i will be suitably preallocated when the functions are called, and should not be reallocated or freed.

  Implement the two functions (along with necessary helper functions) in separate files called insertion_order.c and merge_order.c, along with accompanying header files. Submit these four files (and no others) by email. In particular, although you should test these functions by calling them from a program (containing a main function), please do not submit this test code.

• Assignment 3 (due 18 March): Implement the following algorithms in C. As with assignment 2, implement these with the specified signature in separate files, with no main function, and submit only these files.

  • Heapsort: files heapsort.c, heapsort.h, signature void heapsort(double *x, int n)
  • Randomized quicksort: files quicksort.c, quicksort.h, signature void quicksort(double *x, int n)
  • A variant of the randomized quicksort algorithm in which the partition algorithm chooses three elements randomly, computes their median, and uses it as the pivot: files quicksort3.c, quicksort3.h, signature void quicksort3(double *x, int n)

  In all cases double *x is the input array to be sorted, and int n is the length of the array.

• Assignment 4 (due 31 March): The Towers of Hanoi puzzle consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in order of size on one rod, the smallest at the top. The objective of the puzzle is to move the entire stack to another rod using a sequence of moves. Each move consists of shifting the topmost disk on one rod to the top of another rod, with the restriction that no disk may be placed on top of a smaller disk.

  The assignment is to write a C program that takes a single argument that gives the number of disks, and outputs a sequence of moves that solve the puzzle. The output should consist of one line per move, and each line should have the number of the source and destination towers separated by a space (towers should be numbered 1, 2, 3).

  Here is a possible solution to the puzzle, along with corresponding desired output, when there are five disks.

  Submit only a C file named hanoi.c.

---

Last updated: Tue Apr 9 2013