COP 3502HComputer Science ISpring 2007Instructor: Joseph J. LaViolaHomework 10%Mid term exam 20%COP 3502HComputer Science ISpring 2007http://www.cs.ucf.edu/courses/cop3502h/spr2007/Instructor: Joseph J. LaViolaOffice: Engineering III Room 321 Hours: Tues. 2:30pm-4:00pmemail: [email protected] If you want to email me, MAKE SURE to enter in the subject line “cop 3502h” followedby your name. Teaching Assistant: Sean Szumlanski Engineering III Room 301 Hours: Wed., Thurs. 2:00pm-3:00pm General guidelines This course lays the foundations of computer science. It goes beyond “coding in C”. It will cover different ways to structure the data, and will show how each structure is useful in solving different problems. For each solution, we shall also examine efficiency.This course involves extensive programming, which means besides attending the lecture classes you are required to spend substantial hours in the computer center labs working on your assignments. You may fail this course if you do not submit all the assignments.If you cannot afford to spend time on assignments, it would be in your interest to withdraw from the course. Every student will be given an account on the Olympus. The TAs grading your programs would try to execute your code on Olympus using gcc, or they can try compiling using jgrasp. If your programs cannot run on Olympus or jgrasp, there is no way that the TAs would be able to award you any points for your work. Course Objectives- Provide an introduction to the field of computing: The central concept thatunderlies computer science is the design and implementations of algorithms tosolve specific problems.- Provide Conceptual Content and Software Skills: The lecture componentfocuses on conceptual tools for constructing and analyzing algorithms – TimeComplexity and recursion, while the lab component focuses onimplementation issues involved in C programming.- Introduce elementary data structures: Arranging data in arrays, linked lists,stacks, queues, binary trees and hash tables. - Introduce searching and sorting techniques. . Course ContentWe will cover the following concepts in this course.1. Brief review of Structures, strings, file handling, dynamic memory allocation2. Design of Algorithms for problem solving3. Algorithmic Complexity - Big -O notation, summations4. Searching - linear and binary search5. Recursion - tracing, developing recursive functions, algorithmic complexity usingrecurrence relation6. Stacks and Queues - converting infix expression to postfix form, evaluation ofpostfix forms, waiting line simulation, implementation using arrays7. Linked Lists - Creation, deletion, insertion in sorted linked list, reversing,implementing stack and queue, circularly linked lists8. Binary Trees - tree traversals, tree algorithms, Binary Search Trees, insertion anddeletion, Balanced BST (AVL trees)9. Heap trees - creation, insertion, heapify, deletion10. Hash Table - collision resolving using linear probing, quadratic probing, dynamichashing, double chaining11. Sorting - Selection sort, Insertion sort, Bubble sort, Merge sort, Quick sort, heapsort12. Basic software engineering principles and an introduction to object orienteddesign.Lecture Schedule The sequence of and time spent on the lecture topics given is tentative and may be alteredas the course proceeds.1. Brief review of C: structures, strings, file handling, dynamic memory allocation2. Linked lists3. Stacks and Queues - implementation using arrays, linked lists, circular lists.4. Recursion5. Trees - Binary trees and heap trees, BST, AVL trees6. Algorithm Analysis7. Hash Tables8. Sorting9. Software engineering and object oriented designReference BookWe will use the following textbook: Data structures, algorithms & software principles in CBy: Thomas B. StandishAddison - WesleyAssignments:- All the programming assignments are required to be implemented in ‘C’. You willget an OLYMPUS account, and you can either use the computer labs at UCF, or dial up from home to run your programs on OLYMPUS. Your programs must compile under gcc or cygwin.- All assignments must be submitted through WebCT by 11:59 PM on the indicated due date. You will be allowed 3 late days throughout the course of the semester. Once you have used your late days, assignments submitted after the due date will lose a letter grade for each day late.- Assignments must be carried out individually. Collaboration on any assignment is NOT acceptable. Cheating may result in a failing grade regardless of performance.Exams:There will be one mid term and one final exam.Midterm: March 7thFinal: April 30th All tests will be closed book and notes .Calculators and cell phones are not allowed in any exam/quiz tests. Do NOT miss any test/exam. There are no make-up tests. If you miss a test for SERIOUS reasons you have to provide official written evidence. If evidence is accepted aform of grade recovery will be discussed with the instructor.Cheating may result in a failing grade regardless of performance.Tentative Grading Scheme:Homework 10%Mid term exam 20% Final exam 20%Programming Assignments 50% The instructor reserves the right to use plus/minus grading in this