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
Exercises  Code
examples 2013
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
 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)
 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
 Week1code: 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
Further reading
 C Reference language
 Introduction to Algorithms (2nd Edition), by Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein. McGrawHill
Book.