Course Prerequisites: COP 3223 (Introduction to C Programming)COP 3502H Honors Computer Science I - Spring 2009 SyllabusCourse Prerequisites: COP 3223 (Introduction to C Programming)Class Time: Tuesday and Thursday 8:30 –9:45 amClass Location: HEC 104Course Web Page: http://www.cs.ucf.edu/~dmarino/ucf/cop3502/spr09Lecturer: Arup GuhaOffice: HEC – 240 Email: [email protected] Number: 407-823-1062Office Hours: MWF 8-9am, TR 10-11am or by appointmentCourse Objectives1) Provide an introduction to the field of computing: The central concept that underliescomputer science is the design and implementations of algorithms to solve specific problems.2) Provide Conceptual Content and Software Skills: The lecture component focuses onconceptual tools for constructing and analyzing algorithms – Time Complexity and recursion,while the lab component focuses on implementation issues involved in C programming.3) Introduce elementary data structures: Arranging data in arrays, linked lists, stacks, queues,binary trees and hash tables. 4) Introduce searching and sorting techniques. Course Textbook: Data structures, algorithms & software principles in C, Thomas B. Standish,Addison – Wesley (ISBN – 0-201-59118-9) (Note: Any book on data structures ought to besufficient, since none of the assignments will come directly from the book.)Programming AssignmentsAll programming assignments will be turned in over WebCT. All programs must be done in C.Seven of the course assignments (six programs, one written homework) will be individualassignments, while the project, Connect 4, will be a group assignment. For the first sevenassignments, you may ONLY consult with the TA or me. Details about the group assignment willbe given in class at a later date.Late Assignment PolicyLate homework assignments will be accepted for the first six homework assignments, but will beassessed a late penalty. In particular, assignments will be accepted upto 48 hours after the duedate of the assignment. If an assignment is less than 24 hours late, a 10% penalty will beassessed. If an assignment is in between 24 and 48 hours late, a 20% penalty will be assessed.No late assignments will be accepted on the last programming assignment.Exams For the exams you will typically be allowed a few pages of notes as an aid. The details will bediscussed in the class before each exam. Calculators of any sort are not allowed on exams. Grading The final letter grade will be based upon the five items listed below. Plus/minus grades will beissued, when deemed appropriate.Item PercentageExam #1 20Exam #2 20Final Exam 20Individual Homework Assignments 30Group Programming Assignment 10Also, in order to pass the class you must earn at least a 40% on the final exam. (Thus, if youhave a 75% in the course but earn a 30% on the final, you still get a C- in the course even thoughyour percentage may qualify for a B.)Tentative Schedule Week Tuesday Class Thursday Class AssignmentsJan 7-9 No Class C-Review: structures, string handling, file handling; linear, binary searchJan 12-16 Dynamic memory allocation for arraysRecursion: tracing a recursive function, factorials, reversing a number, printing stringin reverse orderProgram #1: Big Integers (array) (due 1/26)Jan 20-23 Recursion:Fibonacci sequence, recursive binary search, exponentiation, Towersof Hanoi, permutationsIntro to linked lists, creating a linked list, insertions in linked list, copying, deletion, reversingProgram #2: Jumble (due 2/4)Jan 26-30 Linked List Variations: circular, doubly-linked,Big-O notation, algorithm analysis, time complexity problemsProgram #3: Big Integers implemented by linked lists (due 2/17)Feb 2-6 use of summations for algorithm analysis; writing recurrence relations for recursive functionsTime complexity using recurrence relationsHomework #4: Time Complexity Problems (due 2/24)Feb 9-13 EXAM #1 Stacks – implementation using arrays and linked lists, applications (infix to postfix, eval. postfix)Program #5: Something about airplanes (due 3/5)Feb 16-20 Queues – implementation using arrays, linked listsbinary trees, relation of height to number of nodes, tree traversalsFeb 23-27 Tree functions – counting number of nodes with two children, leaf nodesBinary search tree, searching, insertion anddeletion Mar 2-6 Binary search tree functions, Exam #2 ReviewAVL trees, insertionWITHDRAWALDEADLINE!!!Program #6: Word Statistics (due 3/19)Mar 9-13SPRING BREAK SPRING BREAKMar 16-20 AVL tree deletion Backtracking Group Project: Connect Four (due 4/7)Mar 23-27 Min-Max Trees, Tic-Tac-Toe ImplementationSorting- selection sort, insertion sort, bubble sortMar30-Apr3 Review for Exam EXAM #2Apr 6-10 Sorting – merge sort, quick sortConnect 4 Tournament Program #7: Sort of your choice (due4/24)Apr 13-17 Connect 4 Tournament Binary heapsApr 20-24 Hash tables Final Exam ReviewApr 28 Final Exam