Advanced Programming

Tongji University

Fall 2013

---

Lecturer

Maurizio Morisio  , Marco Torchiano
Politecnico di Torino 
email: Maurizio dot morisio  at polito.it
email: marco dot torchiano at polito.it

Communications

Exam 2014 03, grades, solution

Exam 2013 11, grades, solution

Exam 2013 02, grades

Exam 2012 11, grades, solution

Exam solution, solution2,  2009 11  09

Past exam, another

• Shanghai Metro TripHash Contest:
• The initial source code is here (Oct 30 version, changed to used fgets() instead of getline()).
• You have to write the best hash function to get as close as possible to having no collisions (perfection score = 100%).
• You can: change the implementation of the int hash(char* key) function, add additional functions or variables.
• You cannot: change the header or the parameter of the hash function.
• To evaluate your solution you can run the program that will output the number of collisions and the perfection score.

Lectures

• Introduction to course
• C Language recap
• Dynamic Memory Allocation
• Modularity (updated 18-10-2013, stack example and instantiable ADTs)
• Data structures, ADT (updated 8 10 2011) ADT (2012 09 28)
• ADT: Stack and Queue
• Complexity (updated 18-10-2013, empirical measure)
• Lists
• Sorting Algorithms
• Recursion (updated Nov. 2013)
• Hash tables (updated Nov. 2013)

• Heap

• BST (updated Nov. 2013)
• Graphs

Exercises - Code examples 2013

• WeekOne pointers, Stack of int with array, stack of int with linked list
• WeekTwo pointers, malloc, linked list of int
• WeekTwo positional container with bounded array, with linked list. Suggested exercices
• Complete positional container with linked list
• Implement positional container with unbounded array
• Implement Stack with linked list
• Implement stack with un bounded array
• Modular and multi-instance implementation of Stack
• Iterative sorting algorithms
• Dictionaries / Maps: hash tables
• Exercise Metro Trip Stats
• Recursion
• Heap
• BST
• Exam sample discussion and solution.

Exercises - Code examples 2012

• ArrayInt dynamic array of integers
• LinkedList of integers
• ADT 2012 09 29
• Classroom 2012 09 29
• Suggestions: implement Positional container with Linked List
• Suggestions: implement Positional container with Bounded Array
• Suggestions: implement Positional container with Unbounded Array
• ADT 2012 10 12, Modularity, Queue
• Suggestion: implement Queue with Positional container, with circular buffer
• Suggestion: implement Container ordered on key
• Suggestion: implement all ADTs with typedef (instead of int)
• Suggestion: implement all ADTs as modules (ADT.h and ADT.c)
• ADT 2012 10 16
• Suggestion: implement Container ordered on key, with Linked List
• Suggestion: implement Container ordered on key, with Array (bounded, unbounded)
• Hash Table 2012 10 16
• Suggestion: implement Hash Table with chaining, with open addressing
• Discussion of Shanghai metro exam

Exercises - Code examples 2011

• ArrayInt dynamic array of integers
• Stack
• (22 9 2011) implemented with bounded array
• (26 9 2011) implemented with linked list
• (27 9 2011) Implemented with unbounded array
• Queue
• (27 9 2011) implemented with bounded array
• Suggestion: implement queue with unbounded array
• Suggestion: implement queue with linked list
• Positional container (29 9 2011)
• Suggestion: Implement with linked list
• Suggestion: Implement with unbounded array
• Container ordered on key (29 9 2011)
• Suggestion: Implement with linked list
• Suggestion: Implement with unbounded array
• Partial implementation with bounded array, and typedef (8 10 2011)
• Container ordered of students (9 10 2011)
• Container ordered, with binary search (13 10 2011)
• Shanghai Metro – discussion of data structures and algorithms (10 11 2011)
• Recursion, factorial (13 10 2011)
• Memories in C, stack example (13 10 2011)

Exercises - Code examples 2009

• Week1-code: Basic C programs, Memory examples, Stack and Queue
• Ex2:   array, matrix, files exercises: solutions
• Ex3:   array, files, sorting: solutions
• Ex4:   sequence ADT: solution
• Ex5:   students management with sequence ADT: solution
• Ex6:  generic linked list, generic hash table. Students with generic hash table
• Ex7:  generic binary search tree
• Discussion of examples and examples of exams

Tools and Manuals

• DevCpp:   http://sourceforge.net/projects/dev-cpp/
• Eclipse CDT Link : http://www.eclipse.org/cdt/
• XCode: http://developer.apple.com/TOOLS/xcode/
• C Language tutorial
• C reference language

Further reading

• C Reference language
• Introduction to Algorithms (2nd Edition), by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. McGraw-Hill Book.