# CSE 382 Algorithms and Data Structures

## Syllabus

Time & Place:  MW 8:00 - 9:20 CST 3-201 (Undergraduates)
Time & Place:  TH 12:30 - 1:50 CST 3-201 (Graduates)
Lab Sections:  Mo 9:30 - 11:00 & 5:35 - 6:35 Tu 5:00 - 6:00 Fr 3:30 - 4:30
Final Examination Period:  WEDNESDAY MAY 07 @ 8:00-10:00 AM
Instructor:  Barbara Nostrand
Voice:  x3029
Email:  bnostran@syr.edu
WEB:  http://www.deMoivre.org/courses/CSE 382/
Office:  4-293 CST
Office hours: Mo - Th 10:00 - 11:00 AM
Teaching Assistant:  Nancy Khoury
Office hours: We/Th 5:00 - 6:00
Voice:  315-708-????
Email:  nkhoury@syr.edu
Teaching Assistant:  Rajaa Khaled Alqudah
Office hours: Tu/Th 2:30 - 3:30
Voice:  315-708-????
Email:  rkalquda@syr.edu

Course Description

Data structures and algorithms implemented in high-level language.  Nonnumeric processing,  including database management.  Types,  structures,  pointers,  linked lists,  recursion,  iteration,  retrieval,  pattern recognition,  and context processing.

Prerequisites

CSE 283 and CIS/MAT 275 or permission of instructor.

Course Objective

Further develops problem solving and design capablility with an emphasis on effective algorithm design strategies and using data structures to simplify software systems.  Considerable attention is devoted to developing effective software engineering practice,  emphasizing such principles as design,  decomposition,  encapsulation,  procedural abstraction,  testing,  and software reuse.  Familiarity with distributed algorithms,  database systems,  and data modeling.  Upon completing this course,  you should be able to:

• Describe how computer engineering uses or benefits from algorithms.
• Use big "O",  omega,  and theta notation to give asymptotic upper,  lower,  and tight bounds on time and space complexity of algorithms.
• Determine the time complexity of simple algorithms.
• Deduce the recurrence relations that describe the time complexity of recursively-defined algorithms,  and solve simple recurrence relations.
• Design and implement recursive algorithms.
• Design algorithms using the brute-force,  greedy,  and divide-and-conquer strategies
• Employ backtracking,  branch-and-bound,  and heuristic techniques.
• Employ dynamic programming
• Use and implement the fundamental abstract data types including:  hash tables,  binary search trees,  and graphs.
• Employ efficient sorting algorithms.
• Employ depth-first and breadth first search.
• Construct a minimum spanning tree.
• Perform a topological sort.
• Perform tree searches and traversals
• Evaluate algorithms,  select an algorithm from a range of possible options,  justify the choice,  and successfully implement the chosen algorithm.
• Explain the Distributed Algorithm Paradigm.
• Distinguish between logical and physical clocks.
• Describe the relative ordering of events.
• Define the complexity classes P and NP.
• Explain the significance of NP completeness.
• Identify data structures useful to represent specific types of information and discuss the tradeoffs among the different possibilities.
• Implement and employ:  arrays,  records,  strings,  linked lists,  stacks,  queues,  and hash tables.
• Describe the way a computer allocates and represents data structures in memory.
• Design,  implement,  and debug recursive functions and procedures.
• Describe how recursion is typically implemented on the stack

Subject of this Course

Algorithms are fundamental to computer engineering. The real-world performance of any software or hardware system depends on two things: (1) the algorithms chosen,  and (2) the suitability and efficiency of the implementation. Good algorithm design is,  therefore,  crucial for the performance of all systems. Moreover,  the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language,  computer hardware,  or any other implementation aspect.

An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them,  recognizing both the likelihood that multiple reasonable solutions exist and the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of well-defined problems,  recognizing their strengths and weaknesses,  and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area.

Typically,  users of computers have to deal with massive amounts of information on a daily basis; there are e-mails,  documents,  records,  addresses,  web sites and many other kinds of information. In the context of technical development,  there can be specifications,  designs,  tests,  implementations,  different tools and different versions of these tools;  all of these can relate to hardware,  software,  communications,  and so on.  Database systems are designed to maintain and manage large collections of information,  including relationships between elements and access to data.  The computer engineering student needs to be able to develop conceptual and physical data models,  determine what methods and techniques are appropriate for a given problem,  and be able to select and implement an appropriate solution that reflects all suitable constraints,  including scalability and usability.

• Review of object-oriented programming:  Object-oriented methodology,  object-oriented design;  software tools.
• Principles of object-oriented programming:  Inheritance;  class hierarchies;  polymorphism;  abstract and interface classes;  container/collection classes,  and iterators.
• Object-oriented design:  Concept of design patterns and the use of APIs;  modeling tools such as class diagrams, CRC cards, and UML use cases.
• Virtual machines:  The concept of a virtual machine;  hierarchy of virtual machines;  intermediate languages.
• Fundamental computing algorithms:  Introduction to recursive algorithms.
• Introduction to algorithmic analysis:  Average,  and worst case behaviors;  big "O" notation;  empirical measurements of performance.
• Fundamental data structures:  Built-in,  programmer-created,  and dynamic data structures.  Linked structures; implementation strategies for stacks and queues;  strategies for choosing the right data structure.
• Event-driven programming:  Event-handling methods;  event propagation;  exception handling.
• Foundations of human-computer interaction:  Human-centered development and evaluation;  principles of good design and good designers;  engineering tradeoffs;  introduction to usability testing.
• Fundamental techniques in graphics:  Hierarchy of graphics software;  using a graphics API;  simple color models; homogeneous coordinates;  affine transformations;  viewing transformation; clipping
• Software engineering issues:  Tools;  processes;  requirements;  design and testing; design for reuse;  risks and liabilities of computer-based systems.

Units covered:

 CE-ALG1 Basic algorithm analysis 4 Core hours (of 4) CE-ALG2 Algorithmic strategies 8 Core hours (of 8) CE-ALG3 Computing algorithms 9 Core hours (of 12) CE-ALG4 Distributed algorithms 3 Core hours (of 3) CE-ALG5 Algorithmic complexity 2 Core hours (of 2) CE-PRF4 Data structures 10 Core hours (of 13) CE-PRF5 Recursion 3 Core hours (of 5)

Class meetings

Please be sure to attend the correct session of this course. Class time will be used for lecture, discussion, and other challenging activities.  Attendance is required, both physical and mental.  Full participation is expected.  Reading assignments are to be completed before coming to class.  This will better prepare you for asking questions in class, and will facilitate discussion.  Generally, the first meeting each week will be devoted to lecture and discussion and the second class meeting to quizes and discussing programming assignments.  You are expected to complete all homework assignments and projects individually.

Course Materials

• ### Required

• Koffman and Wolfgang Objects, Abstraction, Data Structures and Design Using Java Version 5.0
• Levitin Introduction to the Design and Analysis of Algorithms (2nd Edition)
• Schildt Java: The Complete Reference (Seventh Edition)

• ### Recommended

• Schildt Herb Schildt's Java Programming Cookbook
• Schildt The Art of Java
• Sedgewick Algorithms in C++, Parts 1-4

Laboratory Projects

In this course, you learn by doing.  Thus, you will be asked to complete laboratory projects on a regular basis.  Each of the laboratory assignments is intended to introduce new material and is designed to substantially support the student.  All of the laboratory projects are posted to the web site and should be submitted by the end of the day shown on the schedule.  You will complete these projects with a laboratory partner. A new partner will be assigned each week. In general, you will not work with the same person more than once during the course.

Homework Projects

In this course, you learn by doing. Thus, you will be asked to complete homework projects on a regular basis. Each homework project is designed to develop your individual problem solving skills.  Thus, these projects generally use concepts and techniques previously practiced in a laboratory project and involve much less "hand holding" than was provided in the laboratory project.  All of the homework projects are posted to the web site and should be submitted by the end of the day on the day shown on the schedule.  While you are encouraged to work on laboratory projects with a laboratory partner, you must complete homework projects individually.

Examinations

There will be 2 midterm exams and a cumulative final exam.  Some of the examinations may be written at home.  You must attend the final examination period in order to pass the course.  You must receive a score of 65 or better on a 100 point scale on the final examination to receive better than a D for the course.  More information will be posted on the web as the examination dates near.

Make-up work

Make-up work will be given/accepted only under the following conditions:

1. Someone close to you is very ill, dying, or has died.
2. You are very ill, dying, or have died.
Verification of just cause and advance consultation with the instructor are required before any make-up work will be considered.  Non-medical "emergencies" will be considered on a case-by-case basis.

Grading Policy

Deliverables
 Homework & Projects 600 Examinations 300 Class Participation 100
Grade Distribution
 1000 - 930 A 4 929 - 900 A- 3.7 899 - 870 B+ 3.3 869 - 830 B 3 829 - 800 B- 2.7
 799 - 770 C+ 2.3 769 - 730 C 2 729 - 700 C- 1.7 699 - 600 D 1 599 - 0 F 0

Collaboration and Academic Integrity

The Syracuse University Academic Integrity Policy holds students accountable for the integrity of the work they submit.  Students should be familiar with the Policy and know that it is their responsibility to learn about instructor and general academic expectations with regard to proper citation of sources in written work.  The policy also governs the integrity of work submitted in exams and assignments as well as the veracity of signatures on attendance sheets and other verifications of participation in class activities.  Serious sanctions can result from academic dishonesty of any sort.

Restricted material: Solution guides, pre-written essays and similar materials are "restricted materials". Using such materials will be considered a violation of academic honesty.  You can use any publicly available software library or design tool to help you with your work provided that you are not violating copyright or other legal restrictions or are substantially appropriating a complete piece of software.  If you find a useful design or analysis tool,  please report it to the entire class during the first available project day.  Please be careful to credit the design tools and software libraries that you use in your project documentation.

Academic Honesty: If a breach of academic integrity is discovered,  all involved students will receive a 0 for that assignment or exam.  This may alter your course grade even if a course grade has already been assigned and recorded by the registrar.  Further infractions will be dealt with according to college policy.

Special Needs and Disabilities

Syracuse University's Office of Disability Services authorizes special accomodations for students with disabilities.  If you believe that you are a student who may need academic accomodations due to a disablity,  you must register with the Office of Disability Services (ODS) at 804 University Ave.,  Room 309,  443-4498 or 443-1371 (TDD only).  Please see me during office hours as soon as possible to discuss your needs.  For more inforamtion about services available to you,  please consult the Ofice of Disablity Services.  http://disabilityservices.syr.edu

Formal Attendance and Lateness Policy

Absences: Unavoidable absences do not excuse students from responsibility for course material.  Following a class absence,  you must contact the instructor and attend the next regularly scheduled office hour to receive additional make-up assignments.  These assignments will contribute to the Homework/Quiz/Lab portion of the final grade.  Failure to contact the instructor or turn in the make-up assignment on time will result in a grade of zero for that assignment.  This policy is in effect for unexcused as well as officially excused university absences (e.g.  illness,  religious obligations,  etc.)

Late assignments: Laboratories and projects are due by the end of the day assigned in the schedule.  If you miss an assignment, you must visit a Help Session with the Teaching Assistant in order to turn it in.  Late Laboratory and Project assignments will loose 10% during the first week that they are turned in late,  and will loose an additional 10% for each additional week that they are late.  In case of officially excused absences,  late Laboratory and Project assignments will begin to loose credit on the day following return to school.  No late work will be accepted after the deadline posted in the schedule

Final Examination: Attendance during the Final Examination period is mandatory.  Students failing to attend the scheduled final examination will receive a failing grade for the course.

Statement on Alcohol and Substance Abuse

The mission of the university is to educate the whole person.  As an educator,  I am concerned about the wellbeing of my students both in and out of the classroom.  A student who comes to my class while under the influence of alcohol or other drugs,  or the after effects of that usage,  cannot think critically,  nor can they participate meaningfully.  Any type of intoxication or its effects will not be tolerated in my classroom.  If you think you may be having a problem with alcohol or other substances,  please resach out to a member of our university community for help.

Notice: Policies in this syllabus are subject to change as deemed necessary by the instructor.
Last modified: 2008 JAN 28
bnostran@syr.edu