Saylor.org

Back to Computer Science

Questions? Consult the FAQs!

Search Q&A Center

Introduction to Computer Science II

Purpose of Course  showclose

Course Information  showclose

Welcome to CS102.  General information on the course and its requirements can be found below.

Course Designer: Charles Lively and Yongge Wang
 
Primary Resources: This course is composed of a range of different free, online materials.  However, the course makes primary use of the following resources:

• Stanford University: Julie Zelenski “About the C++ Language”
• Bell Laboratories: Dennis M. Ritchie’s “The Development of the C Language”
• University of Western Australia: Rowan Davies’ "Introduction to Functional Programming”
• Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Introduction to Correctness and Robustness”
• YouTube: Khan Academy’s “Recursive Factorial Function”
• University of Ottawa: Robert C. Holte’s “Recursive Definitions”
• University of Helsinki: Juha Karkkainen’s “STL Functors”

Requirements for Completion: In order to complete this course, you will need to work through each unit and all of its assigned materials, including the quizzes and the final exam.

Note that you will only receive an official grade on your final exam.  In order to “pass” this course, you will need to earn a 70% or higher on the final exam.  Your score on the exam will be tabulated as soon as you complete it.  If you do not pass the exam, you may take it again.

Time Commitment: This course should take you a total of 108.5 hours to complete.  Each unit includes a “time advisory” that lists the amount of time you are expected to spend on each subunit.  These should help you plan your time accordingly.  It may be useful to take a look at these time advisories and determine how much time you have over the next few weeks to complete each unit and then set goals for yourself.  For example, Unit 1 should take you 18.5 hours.  Perhaps you can sit down with your calendar and decide to complete subunits 1.1 (a total of 4 hours) on Monday night, subunit 1.2 (a total of 6 hours) on Tuesday and Wednesday nights, and so forth.

Tips/Suggestions: As noted in the “Course Requirements,” CS101 is prerequisites for this course.  If you are struggling with some program and computer structure concepts as you progress through this course, consider taking a break to revisit CS101.    

This course features a number of Khan Academy™ videos. Khan Academy™ has a library of over 3,000 videos covering a range of topics (math, physics, chemistry, finance, history and more), plus over 300 practice exercises. All Khan Academy™ materials are available for free at www.khanacademy.org.

Learning Outcomes  showclose

Course Requirements  showclose

• Unit 1
• Unit 2
• Unit 3
• Unit 4
• Unit 5
• Unit 6
• Unit 7
• Final Exam
• All Units

Unit Outline show close

Unit 1: C++ and Java  

Having completed CS101: Introduction to Computer Science I, you should have a strong grasp of Java and its uses and a basic understanding of Object-Oriented Programming.  This course will employ both Java and C++, another industry-standard programming language.  In this unit, we will outline the similarities and differences between these two languages, noting how each is used in the industry.  We will also take an in-depth look at the history, importance, and functionality of C++ and compare the basic building blocks of each language in order to draw a distinction between the two and further acquaint you with both languages.

Unit 1 Time Advisory   show close


Unit 1 Learning Outcomes   show close


1.1 History of C++  

1.1.1 Development of C  

• Reading: Bell Laboratories: Dennis M. Ritchie’s “The Development of the C Language”

  Link: Bell Laboratories: Dennis M. Ritchie’s “The Development of the C Language” (HTML)
   
  Instructions: Please read the entirety of this webpage for a solid overview of the history of the C programming language.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

1.1.2 Branching C to C++  

• Reading: Wikipedia: “Compatibility of C and C++”

  Link: Wikipedia: “Compatibility of C and C++” (PDF)
   
  Instructions: Please read the entirety of this webpage for a detailed comparison of the differences between C and the C++ programming language.  This will enable a better understanding of the development of C++.
   
  Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML).  You can find the original Wikipedia version of this article here (HTML).

  See a broken link? Please let us know!

1.1.3 History of Object-Oriented Programming (OOP)  

• Reading: University of Tennessee Department of Electrical Engineering and Computer Science: Jian Huang’s “A Brief History of Object-Oriented Programming”

  Link: University of Tennessee Department of Electrical Engineering and Computer Science: Jian Huang’s “A Brief History of Object-Oriented Programming” (HTML)
   
  Instructions: Please read the entirety of this webpage for a detailed overview of the history of object-oriented programming.  It will highlight the first OOP language, and the advances made to recent programming languages that use OOP concepts.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

1.2 C++ and Java in Industry  

1.2.1 Influence of Prevalence of C  

• Reading: The University of Leicester: Dr. Richard Mobbs’ “Introduction to C Programming”

  Link: The University of Leicester: Dr. Richard Mobbs’ “Introduction to C Programming” (HTML)
   
  Instructions: Read Sections C (Overview of to C Programming), D (Running C Programs), and E (Structure of C Programs).  In the table of contents on the left side of the webpage, click on the hyperlink for each title in these sections to access the text.  Note that this reading provides information about the uses of C in industry and academia.  This will be important to understanding the evolution of other programming languages.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

1.2.2 Java Overview  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Chapter 1: Overview: The Mental Landscape”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Chapter 1: Overview: The Mental Landscape” (PDF)
   
  Instructions: Read Sections 1-7.  This reading will explore the mechanisms of the Java programming language and explain how the language is used appropriately.
   
  Terms of Use: The linked material above is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 License and can be viewed in its original from here.  

  See a broken link? Please let us know!

1.2.3 C++ Overview  

• Lecture: Stanford University: Julie Zelenski “About the C++ Language”

  Link: Stanford University: Julie Zelenski “About the C++ Language” (YouTube)
  
  Also available in:
  iTunes U
  
  Instructions: Please view Lecture 27 in its entirety (41:33 minutes) for a detailed understanding of how C++ is used outside of the typical programming course.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

1.3 C++/Java Comparison  

• Reading: Austin Community College: Richard Baldwin’s “Similarities and Differences between Java and C++”

  Link: Austin Community College: Richard Baldwin’s “Similarities and Differences Between Java and C++” (HTML)
  
  Instructions: Read through the lecture notes on this page to get a detailed understanding of the similarities and differences between Java and C++.  This reading covers sections 1.3.1-1.3.6.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Lecture: Stanford University: Julie Zelenski “Similarity between C++ & Java: Syntax, Variable Types, Operators, Control Structures”

  Link: Stanford University: Julie Zelenski “Similarity between C++ & Java: Syntax, Variable Types, Operators, Control Structures” (YouTube)
  
  Also available in:
  iTunes U
  
  Instructions: Please view Lecture 2 in its entirety (43:47 minutes) for a detailed understanding of the similarities in structure between the C++ and Java programming languages.  This lecture covers the following topics: Variables, Literals, and Data Types, Operators, Functions, File I/O, Classes and Objects, and Memory Management Schemes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 1 Activities and Assessments  

• Activity: The Saylor Foundation’s “Creating Basic Hello World Programs in C++ and Java”

  Link: The Saylor Foundation’s “Creating Basic Hello World Programs in C++ and Java” (PDF)
  
  Instructions: Please click on the link above, and follow the instructions to complete this assignment. 
   
  This activity should take you 1 hour to complete.

  See a broken link? Please let us know!

• Activity: The Saylor Foundation’s “Obtaining User Input in C++ and Java”

  Link: The Saylor Foundation’s “Obtaining User Input in C++ and Java” (PDF)
  
  Instructions: Please click on the link above, and follow the instructions to complete this assignment.
  
  This activity should take you 1.5 hours to complete.

  See a broken link? Please let us know!

• Assessment: The Saylor Foundation’s “Creating For Loops in C++ and Java”

  Link: The Saylor Foundation’s “Creating For Loops in C++ and Java” (PDF) and “Answer Key to Creating Loops in C++ and Java” (PDF).
  
  Instructions: Please click on the link above, and follow the instructions to complete this assessment.  When you have completed the assessment, check your answers with the answer key.
  
  Completing this activity should take approximately 1 hour.

  See a broken link? Please let us know!

• Assessment: The Saylor Foundation’s "Creating Arrays in C++ and Java"

  Link: The Saylor Foundation’s “Creating Arrays in C++ and Java” (PDF) and “Answer Key to Creating Arrays in C++ and Java” (PDF).
  
  Instructions: Please click on the link above, and follow the instructions to complete this assessment.  When you have completed the assessment, check your answers with the answer key.
  
  Completing this activity should take approximately 1 hour.

  See a broken link? Please let us know!

Unit 2: The Building Blocks of Object-Oriented Programming  

Now that you are familiar with both C++ and Java, you are ready to explore more advanced topics in Object-Oriented (OO) Programming.  We will begin by discussing the motivation behind programming with objects, learning the essential characteristics of OO Programming languages and identifying the advantages and disadvantages of various major programming frameworks.  The unit will also provide a general history of OO Programming and, finally, review major characteristics of OO Programming.  By the end of the unit, you will be able to discuss different programming paradigms and identify the main properties of OO Programming. 

Unit 2 Time Advisory   show close


Unit 2 Learning Outcomes   show close


2.1 Programming Paradigms  

• Reading: University of Western Australia: Rowan Davies’ “Introduction to Functional Programming”

  Link: University of Western Australia: Rowan Davies’ “Introduction to Functional Programming” (PDF)
  
  Instructions: Scroll down the webpage (about 2/3 down the page) to the table titled “Part I- Functional Programming.”  Then, please click on the appropriate PDF hyperlink for lecture 2 entitled “Functional Programming-Introduction.”  Read through these lecture notes (17 pages) for a detailed understanding of the differences between functional programming and imperative programming paradigms.  This reading the following topics: functional, imperative, and logic.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Reading: Aalborg University: Kurt Normark’s “Overview of the Four Main Programming Paradigms”

  Link: Aalborg University: Kurt Normark’s “Overview of the Four Main Programming Paradigms” (HTML)
   
  Instructions: Read through these lecture notes for a detailed understanding of the differences between the four most common programming paradigms: functional, imperative, logic, and object-oriented.  This reading covers subunits 2.1.3 and 2.1.4.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Lecture: Academic Earth: University of California, Berkeley: Brian Harvey’s “Object-Oriented Programming I”

  Link: Academic Earth: University of California, Berkeley: Brian Harvey’s “Object-Oriented Programming I” (YouTube)
   
  Instructions: Please watch this 50-minute lecture for a detailed understanding of the various data types used in Object-Oriented programming.  Specifically, this lecture will present various programming examples and higher-order programming types.  This reading covers the following topics: Why Program with Objects and comparison to Other Paradigms.
   
  Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.  It is attributed to Brian Harvey and the original version can be found here (HTML).

  See a broken link? Please let us know!

2.2 Fundamental Concepts of Object-Oriented Programming  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Chapter 5: Programming in the Large II- Objects and Classes”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Chapter 5: Programming in the Large II” (PDF)
   
  Instructions: Read all of Chapter 5, which includes sections 1 through section 6 of the online textbook Introduction to Programming Using Java.  This material covers topics for sections 2.2.1-2.2.4.
   
  Terms of Use: Terms of Use: The linked material above is licensed under  Creative Commons Attribution-Noncommercial-ShareAlike 3.0 License and can be viewed in its original form here.  

  See a broken link? Please let us know!

2.2.1 Classes and Objects  

• Assessment: The Saylor Foundation’s “Understanding Classes and Objects in Java”

  Link: The Saylor Foundation’s “Understanding Classes and Objects in Java” (PDF) and “Answer Key to Creating Classes and Objects in Java” (PDF).
   
  Instructions: Please click on the link above, and follow the instructions to complete this assessment.  When you have completed the assessment, check your answers with the answer key.

  See a broken link? Please let us know!

2.2.2 Inheritance  

• Assessment: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Review for Chapter 5”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Review for Chapter 5”(PDF)
  
  Instructions: Please complete the review sheet.
  
  Terms of Use: The linked material above is licensed under  Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License and can be viewed in its original form here.

  See a broken link? Please let us know!

• Assessment: The Saylor Foundation’s “Understanding Inheritance in Java”

  Link: The Saylor Foundation’s “Understanding Inheritance in Java” (PDF)
  
  Instructions: Please click on the link above, and follow the instructions to complete this assessment.  When you have completed the assessment, check your answers against The Saylor Foundation’s “Answer Key to Understanding Inheritance in Java” (PDF).  This assessment covers the topics of encapsulation and polymorphism.

  See a broken link? Please let us know!

Unit 2 Quiz and Assessment  

• Assessment: Java.net’s “Basic Concepts about Object Orientation”

  Link: Java.net’s “Basic Concepts about Object Orientation” (HTML)
  
  Instructions: By clicking the on link above, you will access 33 quizzes of the “Basic Concepts about Object Orientation”.  After finishing the quizzes, you can click the “Click here to see the suggested answers” link to see the solutions.
  
  Completing these 33 quizzes should take approximately 30 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

  Submit Materials

• Reading: The Saylor Foundation’s “Unit 2 Assessment”

  Link: The Saylor Foundation’s “Unit 2 Assessment”
  
  Instructions: Please complete this assessment to check your understanding of the topics covered in this unit.

  See a broken link? Please let us know!

Unit 3: C++ Standard Template Library  

Nearly every C++ programmer uses the C++ Standard Template Library (STL), a powerful and highly useful library of generic-typed data structures and algorithms.  In this unit, we will learn how and why the STL was originally developed.  The unit will also introduce you to the history and basics of templates and generic programming before presenting the structures (Containers, Iterators, and Functors) and algorithms that the Standard Template Library contains.  By the end of this unit, you will be familiar with the STL, its uses, and its structures and algorithms.

Unit 3 Time Advisory   show close


Unit 3 Learning Outcomes   show close


3.1 History and Motivation  

• Reading: Wikibooks: “Ada Programming/Generics”

  Link: Wikibooks: “Ada Programming/Generics” (PDF)
   
  Instructions: Read this section in Wikibooks for an explanation of the history and purpose of generic programming and the precursor language, Ada.  These chapters cover all of subunit 3.1, including sections 3.1.1 and 3.1.2.  Note: Adais an Object-Oriented programming language used predominantly in military applications.  It shares many of its features—including its structure and typing, with C++.  While both languages were developed in the same year, Ada’s rapid adoption by certain circles within the Computer Science world led computer scientists to modify C++ by adopting some of Ada’s features in subsequent C++ releases.  These changes are seen as an important evolutionary step in Object-Oriented programming.  These materials cover generic programming, precursor Ada, and ANSI/ISO.
   
  Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML).  You can find the original Wikibooks version of this article here (HTML).

  See a broken link? Please let us know!

• Reading: InformIT: Andrew Binstock’s “An Interview with Alexander Stepanov and Paul McJones on Elements of Programming”

  Link: InformIT: Andrew Binstock’s “An Interview with Alexander Stepanov and Paul McJones on Elements of Programming” (HTML)
  
  Instructions: Please read this article for a detailed interview with Alexander Stepanov and Paul McJones, who are largely responsible for the Standard Template Library and several methods component of Generic programming.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

3.2 Main Design Ideas  

• Reading: Dartmouth College: Afra Zomorodian’s “Computer Architecture”

  Link: Dartmouth College: Afra Zomorodian’s “Computer Architecture” (HTML)
  
  Instructions: Please read the following lecture in its entirety for a detailed explanation of how computer structure affects programming techniques and approaches.  This lecture provides a detailed understanding of the affects that modern computer organization has on programming.  This reading covers the following topics: ALU, von Neumann computation model, memory control, and organization.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

3.3 Elements of C++ STL  

• Reading: University of Helsinki: Juha Karkkainen’s “Standard Template Library, STL”

  Link: University of Helsinki: Juha Karkkainen’s “Standard Template Library, STL” (HTML)
  
  Instructions: Read this outline for an introduction to the importance of the standard template library and the elements that make up STL.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

3.3.1 Containers  

• Reading: University of Helsinki: Juha Karkkainen’s “STL Containers”

  Link: University of Helsinki: Juha Karkkainen’s “STL Containers” (HTML)
  
  Instructions: Read this text for an understanding of the fundamental aspects of Containers in STL.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

3.3.2 Iterators  

• Reading: Algorithmic Solutions’ “Introduction to Iterators”

  Link: Algorithmic Solutions’ “Introduction to Iterators” (HTML)
  
  Instructions: Read this webpage for an understanding of the fundamental aspects of Iterators in STL.
  
  Terms of Use: Please respect the copyright and terms of use.    

  See a broken link? Please let us know!

3.3.3 Complexity and Cost  

• Lecture: Massachusetts Institute of Technology: Eric Grimson and John Guttag’s “Complexity”

  Link: Massachusetts Institute of Technology: Eric Grimson and John Guttag’s “Complexity” (YouTube)
  
  Also available in:
  Adobe Flash, PDF Transcript, MP4 Download
  iTunes U
  
  Instructions: Please watch this 50-minute video for an understanding of the fundamental aspects of complexity and cost in programming.
  
  Terms of Use: Eric Grimson and John Guttag, Introduction to Computer Science and Programming, Fall 2008. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011).  License: Creative Commons BY-NC-SA 3.0.  The original version can be found here.

  See a broken link? Please let us know!

3.3.4 Functors  

• Reading: University of Helsinki: Juha Karkkainen’s “STL Functors”

  Link: University of Helsinki: Juha Karkkainen’s “STL Functors” (HTML)
  
  Instructions: Read this section for an understanding of the fundamental aspects of Functors in STL.  This reading covers operator and predicates.
  
  Terms of Use: Please respect the copyright and terms of use.

  See a broken link? Please let us know!

Unit 3 Assessment  

• Assessment: Tech Interviews’ “Advanced C++ and STL Interview Questions”

  Link: Tech Interviews’ “Advanced C++ and STL Interview Questions” (HTML)
  
  Instructions: By clicking the on link above, you will access a couple interview questions for C++ and STL.  Try to think about the answers to these questions before you read the answers.
  
  Completing this assessment should take approximately 30 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 4: Exceptions  

A programmer must ensure the safe execution of his or her code.  In other words, if an error occurs, the program should present the user with relevant information and then quit gracefully.  The built-in C++ structures used to accomplish this goal are known as “Exceptions.”  This unit will introduce you to the concept of throwing and catching Exceptions when something goes wrong with your software, explain how they are used in both C++ and Java, and teach you how to handle them.  By the end of this unit, you will be able to write safe programs designed to perform gracefully when/if errors occur.

Unit 4 Time Advisory   show close


Unit 4 Learning Outcomes   show close


4.1 Exceptions: Definition and Role  

• Web Media: YouTube’s “Java Tutorial - 21 - Exception Handling”

  Link: YouTube’s “Java Tutorial - 21 - Exception Handling” (YouTube)
   
  Instructions: Please watch this video, where the instructor explains the exceptional handling in Java programming language.
   
  Watching this video should take approximately 5 minutes.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

4.1.1 Traditional Error-Handling Method  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Introduction to Correctness and Robustness”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Introduction to Correctness and Robustness” (PDF)
  
  Instructions: Please read the entirety of this article for a solid introduction to what makes a program correct and the results that should be obtained if a program provides erroneous output.
  
  Terms of Use: The linked material above is licensed under  Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License and can be viewed in its original form here.

  See a broken link? Please let us know!

4.1.2 Benefits of Exceptions and Writing Correct Programs  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Writing Correct Programs”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Writing Correct Programs” (PDF)
  
  Instructions: Please read the entirety of this article for a detailed understanding of writing correct programs and an introduction to using exceptions within a program.
  
  Terms of Use: Terms of Use: The linked material above is licensed under  Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License and can be viewed in its original form here.

  See a broken link? Please let us know!

4.2 Exceptions in Java and C++  

4.2.1 Exception Class in Java  

• Reading: Andrews College: Gregory Kesden’s “Exception Handling”

  Link: Andrews College: Gregory Kesden’s “Exception Handling in Java” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview on the role that exception handling has in the Java programming language.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

4.2.2 C++ Exception Library  

• Reading: Notes on C++: Robert Burkhardt’s “Exceptions in C++”

  Link: Notes on C++: Robert Burkhardt’s “Exceptions in C++” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview of the role of exceptions generated by the C++ library.  This reading covers throw and try/catch concepts.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 4 Assessment  

• Assessment: J2EE Programmer: “Catching Exceptions in Java”

  Link: J2EE Programmer: “Catching Exceptions in Java” (HTML)
  
  Instructions: Please take the following assessment after completing all of Unit 4.  It provides a test of the higher-level concepts involved in Exceptions using a Java programming example.  After you have selected your answers, click on the “Explanation” hyperlink at the bottom of the webpage to check your answers.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 5: Recursion  

Often considered one of the more conceptually difficult concepts within the field of Computer Science, recursion – the act of a function invoking itself – is a powerful and relevant tool for any Computer Scientist.  In this unit, we will take an in-depth look at recursion, learning the recursive steps, the role that recursion plays in common data structures, and what happens inside the computer when a recursion function is invoked.  By the end of this unit, you will recognize situations that require recursion and be able to apply it appropriately.

Note: Recursion can be a difficult concept for some students new to the field of Computer Science.  This anxiety is best resolved through the use of an example.  For this module, we will employ the use of recursion to write a program to express the “factorial” function.  This straight-forward example will give the student an overview of all the major components of recursion.

Unit 5 Time Advisory   show close


Unit 5 Learning Outcomes   show close


5.1 Definition  

• Reading: University of Ottawa: Robert C. Holte’s “Recursive Definitions”

  Link: University of Ottawa: Robert C. Holte’s “Recursive Definitions” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview on recursion, its role in programming, and everyday examples of recursion.  This reading covers subsections 5.1.1 and 5.1.5.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

5.1.1 Divide and Conquer  

• Reading: University of Ottawa: Robert C. Holte’s “Using Recursion to Solve Problems”

  Link: University of Ottawa: Robert C. Holte’s “Using Recursion to Solve Problems” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview on recursion, its role in programming, everyday examples of recursion, and how recursion can be used to solve problems.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

5.1.2 Applications to Programming  

• Reading: University of Ottawa: Robert C. Holte’s “Recursion as a Programming Technique”

  Link: University of Ottawa: Robert C. Holte’s “Recursion as a Programming Technique” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview on recursion and how it is used as a programming technique.  This material also covers section 5.1.3.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

5.1.3 Recursive Structure  

• Lecture: Massachusetts Institute of Technology: Eric Grimsom and John Guttag’s “Divide and Conquer Methods”

  Link: Massachusetts Institute of Technology: Eric Grimsom and John Guttag’s “Divide and Conquer Methods” (YouTube)
  
  Also available in:
  Adobe Flash, PDF Transcript, Mp4 Download
  iTunes U
  
  Instructions: Please watch this 46-minute lecture on the nature of recursive structure.  Specifically, this lecture explains the theory of divide and conquers algorithms.
  
  Terms of Use: Eric Grimson and John Guttag, Introduction to Computer Science and Programming, Fall 2008. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0.  The original version can be found here.

  See a broken link? Please let us know!

5.1.4 Steps  

• Reading: Saint Vincent College’s Tutorial on Recursion: “Software Design Using C++: Recursion”

  Link: Saint Vincent College’s Tutorial on Recursion: “Software Design Using C++: Recursion” (HTML)
  
  Instructions: Please click on the link above and read the entire webpage.  This link describes the recursion process and discusses the base case or stopping case that stops the recursive procedure.  The article discusses recursive functions for factorial and Fibonacci numbers as well as recursive sorting algorithms such as merge sort and quick sort.  Note that this reading will cover the material you need to know for subunits 5.1.4.1 and 5.1.4.2.
  
  Reading this tutorial should take approximately 2 hours.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

5.1.4.1 Base Case  

Note: This subunit is covered by the reading assigned beneath subunit 5.1.4.  In particular, pay attention to the base case, which is referred to as “stopping case” in the reading.  You will learn that base case is required in a recursive function; otherwise, the recursion will go on forever.

5.1.4.2 Recursive Step  

Note: This subunit is covered by the reading assigned beneath subunit 5.1.4.  In particular, pay attention to the fact that in recursive function call, the function calls itself, but with different parameters.  This chain of recursive calls goes on until the base case is reached.  At this point, the recursion ends and returns the computed value.

5.1.5 Recursion Examples  

• Web Media: YouTube: TheNewBoston’s “Bucky’s C++ Programming Tutorials - 31 - Recursion”

  Link: YouTube: TheNewBoston’s “Bucky’s C++ Programming Tutorials - 31 - Recursion” (YouTube)
  
  Instructions: Please watch this 10-minute video, as it demonstrates how a recursive function is written.  This video demonstrates recursive function for finding the factorial of a number.  To better understand this material, please write this program in your computer using C++ and compile it.  After successful compilation, run this program.
  
  Watching this video and writing this program should take approximately 30 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Web Media: Khan Academy’s “Recursive Factorial Function”

  Link: Khan Academy’s “Recursive Factorial Function” (YouTube)
  
  Instructions: Please watch this video, as the instructor explains the recursive factorial function in Python programming language.
  
  Watching this video should take approximately 5 minutes.
  
  Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.  It is attributed to the Khan Academy.

  See a broken link? Please let us know!

• Lecture: Khan Academy’s “Exercise – Write a Fibonacci Function,” “Iterative Fibonacci Function Example,” “Stepping through Iterative Fibonacci Function,” “Recursive Fibonacci Example,” and “Stepping through Recursive Fibonacci Function”

  Link: Khan Academy’s “Exercise – Write a Fibonacci Function”, “Iterative Fibonacci Function Example”, “Stepping through Iterative Fibonacci Function”, “Recursive Fibonacci Example”, and “Stepping through Recursive Fibonacci Function” (YouTube)
  
  Instructions: Please click on the first link above, and watch the lecture on Fibonacci numbers in its entirety (4 minutes).  In this series of short lectures, we’ll examine recursion by going through the stages of the programming process to implement a recursive function.  Briefly, a recursive function is a function that calls itself.
  
  In the Khan lectures we use Python, which is an easy-to-use procedural and object-oriented language, but our focus will not be on the syntax of the language.  Rather, our focus is the concept of recursion, the requirements for the program (i.e., the statement of the problem), the design of the program, the semantics of the program (this is the stage in which we don’t worry too much about the syntax of Python – knowing Java and C++ enables you to learn Python easily), and the verification of the program implementation (we do this by stepping through the program and running several test cases).
  
  Computer science and programming have strong ties with mathematics, and recursion may remind you of a proof method in mathematics called mathematical induction, which is typically used when we want to prove a statement involving the natural numbers, i.e., “n.”  To prove the statement involving “n,” we: 1) prove the statement for a base case, usually n = 1; 2) assume the statement is true for n-1; 3) then prove the statement for “n,” using steps 1 and 2.  So, get started, and watch the first video, which gives the requirements for the program to be written.
  
  Then, view the second lecture (7 minutes), which uses an iterative design to satisfy the requirements.  Remember that this subsection is on recursion.  So why do we look at iteration?  We use an iterative example to help us better understand recursion, to show that requirements (or programming problems) can have several program implementations, and to enable you to compare iteration and recursion.  This design makes use of a list data structure.  After implementing an iterative design, (i.e., writing the progam), Khan runs it to demonstrate that it works correctly for several test cases.
  
  Next, view the third lecture (10 minutes), which presents some verification of the iterative design by stepping through the program implementation, line by line and variable by variable.
  
  Next, watch the fourth lecture (8 minutes), which now uses a recursive design to satisfy the requirements.  This recursive implementation uses a string data structure to print out the successive calls of the function to itself.  This recursive implementation is tested using several inputs.  Note that the calls show that the call for “n” makes use of the call for “n-1,” etc. (i.e., the mathematical inductive step 2 above).
  
  You should compare this recursive implementation with the iterative implementation.  If you have to find a series of natural numbers, and you are given the first two (called the base cases) as well as the rule for calculating the next integer in the series, you can apply the rule sequentially, finding the third, the fourth, the fifth, etc., until you find the nth.  A program that implements this manual approach is the iterative program; such an approach needs a data structure to store all the integers up to the nth one.
  
  Another approach assumes that we can express the rule as a formula.  For example, the nth term = (n-1)st term + (n-2)nd term; this can be expanded to, nth term = (n-2)nd term + 2* (n-3)re term + (n-4)th term; and this expansion can be continued to result in as many terms as needed to give an expression that calculates the nth term.  To find the nth term, all you would have to do is enter the base cases into the formula and do one calculation (no iterating).  The recursive function, in effect, does this.  The general formula is programmed: fibonacci (n) = fibonacci (n-1) + fibonacci (n-2).  This general recursive formula is automatically calculated for us by the interpreter.  The interpreter uses an internal data structure, a stack, to implicitly calculate the formula by “iterating” through the stack—i.e., the interpreter does the iteration for us.
  
  Finally, view the fifth and last lecture (8 minutes), which presents some verification of the design and implementation by stepping through the program, line by line and function call by function call.  (We say “some” because there are other verification techniques that can be used, depending on how much assurance is needed for correct execution of the program to satisfy various users and various needs.)
  
  Viewing the lectures and taking notes should take approximately 50 minutes to complete.
  
  Terms of Use: These videos are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.  They are attributed to the Khan Academy.

  See a broken link? Please let us know!

5.2 Recursive Algorithms  

• Reading: Old Dominion Univeristy: Shunichi Toida’s “Recursive Algorithm”

  Link: Old Dominion Univeristy: Shunichi Toida’s “Recursive Algorithm” (HTML)
  
  Instructions: Please read the entirety of this webpage for an introduction on recursive algorithms.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Lecture: Stanford University: Julie Zelenski’s “Thinking Recursively”

  Link: Stanford University: Julie Zelenski’s “Thinking Recursively” (YouTube)
  
  Also available in:
  iTunes U
  
  Instructions: Please watch Lecture 9 for a detailed lecture on recursive algorithms and how to apply recursion to various algorithms.  The examples and patterns presented include recursive tree calls, towers of Hanoi, and permutations.
  
  Watching this lecture should take approximately 45 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 5 Assessment  

• Assessment: Washington University in St. Louis: Kenneth J. Goldman’s “Recursion Practice Problems”

  Link: Washington University in St. Louis: Kenneth J. Goldman’s “Recursion Practice Problems” (HTML)
  
  Instructions: By clicking the on link above, you will access 10 practice problems based on a small recursive program.  Try to answer these questions before.  It should take you approximately 30 minutes to complete this assessment.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the web page above.

  See a broken link? Please let us know!

Unit 6: Searching and Sorting  

As a computer programmer, you will need to know how to search and sort data.  This will require you to leverage what you have learned in a number of different Computer Science areas, drawing from your introduction to data structures and algorithms in particular.  In this unit, we will identify the importance of searching and sorting, learn a number of popular searching and sorting algorithms, and determine how to analyze and appropriately apply them.  By the end of this unit, you will recognize instances in which you need a searching or sorting algorithm and be able to apply one efficiently.

Unit 6 Time Advisory   show close


Unit 6 Learning Outcomes   show close


6.1 Search Algorithms  

6.1.1 List Search  

• Reading: University of Ottawa: Robert C. Holte’s “Our Specification of Lists - General Considerations”

  Link: University of Ottawa: Robert C. Holte’s “Our Specification of Lists - General Considerations” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview of the list data structures in programming and how they are used.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.1.2 Tree Search  

• Reading: University of Ottawa: Robert C. Holte’s “Introduction to Trees”

  Link: University of Ottawa: Robert C. Holte’s “Introduction to Trees” (HTML)
  
  Instructions: Please read the entirety of this webpage for an introduction to tree structures.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.1.2.1 Tree Search Algorithms  

• Reading: University of California-Irvine: David Eppstein’s “Breadth-First Search and Depth-First Search”

  Link: University of California-Irvine: David Eppstein’s “Beadth-First Search and Depth-First Search” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview tree traversal in programming.  This reading covers breadth-first, depth-first, and graph search concepts.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Reading: University of California-Irvine: David Eppstein’s “Graph Algorithms”

  Link: University of California-Irvine: David Eppstein’s “Graph Algorithms” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid overview of various graph algorithms in programming.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.2 Sorting Algorithms  

• Reading: University of Ottawa: Robert C. Holte’s “General Sorting Strategy”

  Link: University of Ottawa: Robert C. Holte’s “General Sorting Strategy” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to sorting techniques and its uses.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.2.1 Merge Sort  

• Web Media: YouTube: Xoax.net’s “Merge Sorting”

  Link: YouTube: Xoax.net’s “Merge Sorting” (YouTube)
  
  Instructions: Please watch this video, as the instructor explains the merge sorting algorithm.
  
  Watching this video should take approximately 5 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.2.2 Insertion Sort  

• Web Media: YouTube: Xoax.net’s “Insertion Sorting”

  Link: YouTube: Xoax.net’s “Insertion Sorting” (YouTube)
  
  Instructions: Please watch this video, as the instructor explains insertion sorting algorithm.
  
  Watching this video should take approximately 4 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Lecture: Khan Academy’s “Exercise – Write a Sorting Function,” “Insertion Sort Algorithm,” “Insertion Sort in Python,” “Stepping through Insertion Sort Function,” and “Simpler Insertion Sort Function”

  Link: Khan Academy’s “Exercise – Write a Sorting Function”, “Insertion Sort Algorithm”, “Insertion Sort in Python”, “Stepping through Insertion Sort Function”, and “Simpler Insertion Sort Function” (YouTube)
  
  Instructions: Please click on the first link above and watch the lecture in its entirety (4 minutes).  This lecture specifies the requirements for the program.  Again, our focus in this series of short lectures is not the syntax of the programming language used (i.e., Python), but the design (or algorithm) of the program and the data structures used.  View the second video (8 minutes), which designs the program.  This design makes use of the list data structure and For and While control constructs.
  
  Next, view the third video (9 minutes), which implements the design in Python—the simple procedural and object-oriented language used in the Khan lectures.  Then, view the fourth video (12 minutes), which verifies the Python design and implementation by stepping through the program, line by line and function call by function call.  Note that comments are used within the program to document design and implementation decisions or choices.
  
  Finally, view the fifth video (3 minutes).  This video demonstrates the next stage of the programming process.  Previously, we demonstrated the requirements, design, implementation, and verification stages of programming.  The next stage illustrated in this lecture is maintenance.  There are two types of maintenance: fixing bugs or errors in the program, and enhancements.  This lecture enhances the program by improving its efficiency (relative to the number of statements used).
  
  Watching these lectures and taking notes should take approximately 1 hour.
  
  Terms of Use: These videos are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.  They are attributed to the Khan Academy.

  See a broken link? Please let us know!

6.2.3 Quick Sort  

• Reading: AlgoList’s “Algorithms and Data structures: Quick Sort”

  Link: AlgoList’s “Algorithms and Data structures: Quick Sort” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to quick sort techniques.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Web Media: YouTube: Xoax.net’s “Quick Sorting”

  Link: YouTube: Xoax.net’s “Quick Sorting” (YouTube)
  
  Instructions: Please watch this video, as the instructor explains quick sorting algorithm.
  
  Watching this video should take approximately 5 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.2.4 Radix Sort  

• Reading: University of Ottawa: Robert C. Holte’s “Radix Sort”

  Link: University of Ottawa: Robert C. Holte’s “Radix Sort” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to radix sort techniques.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

6.2.5 Analysis  

• Reading: University of Texas-San Antonio: Daniel Jimenez’s “Complexity Analysis”

  Link: University of Texas-San Antonio: Daniel Jimenez’s “Complexity Analysis” (HTML)
  
  Instructions: Please read the entirety of this webpage to learn the basics of time complexity in programming and computer science.  This section covers time complexity, identify the best algoirhtms for your application, and big-Oh notations.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Web Media: CSAnimated’s “Big O Notation” (Flash)

  Link: CSAnimated’s “Big O Notation” (Flash)
   
  Instructions: Please watch this slideshow, which contains audio, and listen as the instructor explains Big O notation.  As you view these slides, you will understand that Big O describes the effect of the size of the input number on an algorithm’s performance.  The instructor explains how the complexity of an algorithm is computed by giving a simple example and walking through the steps needed to find the complexity of a function.
   
  Studying this material should take approximately 1 hour.
   
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 6 Assessment  

• Assessment: Proprof: RosyU’s “Quick Sort Quiz”, “Insertion Sort Quiz”, and “Merge Sort Quiz”

  Link: Proprof: RosyU’s “Quick Sort Quiz”, “Insertion Sort Quiz”, and “Merge Sort Quiz” (HTML)
  
  Instructions: By clicking the on links above, you will access 14 quizzes.
  
  Completing this assessment should take approximately 30 minutes.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Unit 7: Template Programming  

In an earlier unit, we discussed the C++ Standard Template Library and introduced the concept of template programming.  In this unit, we will further explore both templates and generic programming, cultivating a broader understanding of the topic.  We will begin with a review of the STL and a discussion of the motivation behind template development.  We will then discuss templates in a more generic fashion, referring back to the STL where necessary, and take a look at how templates are utilized within Java, comparing and contrasting with the C++ STL.  By the end of this unit, you will recognize the importance of templates, be able to identify when they are needed, and know how to apply them efficiently.

Unit 7 Time Advisory   show close


Unit 7 Learning Outcomes   show close


7.1 Generic Programming  

• Reading: Max Planck Institut Informatik: Lutz Ketter’s “STL and Generic Programming”

  Link: Max Planck Institut Informatik: Lutz Ketter’s “STL and Generic Programming” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to the standard template library and generic programming.  This reading covers STL definition, benefits, reusability, multiple inheritance, and operator overloading.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

7.2 Templates in C++  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Generic Programming”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Generic Programming” (PDF)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to the standard template library and generic programming.  This reading covers standard template library, containers, algorithms, compile time polymorphism vs. runtime polymorphism, and template types.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
  
  Terms of Use: The linked material above is licensed under Creative Commons Attribution-Noncommercial-ShareAlike 3.0 License and can be viewedin its original form here.

  See a broken link? Please let us know!

• Lecture: Stanford University: Julie Zelenski’s “Rules of Template Implementation”

  Link: Stanford University: Julie Zelenski’s “Rules of Template Implementation” (YouTube)
  
  Also available in:
  iTunes U
  
  Instructions: Please watch Lecture 19 in its entirety (41:26 minutes) for a detailed understanding of template types and implementations in the C++ programming language.  This lecture gives a detailed explanation of function templates and the class templates.  This lecture will provide information that also covers the following topics: function templates, class templates, templates in Java, and history of generic programming in Java.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

• Lecture: University of California, Berkeley: Paul Hilfinger’s “Generic Programming”

  Link: University of California, Berkeley: Paul Hilfinger’s “Generic Programming” (Flash)
  
  Instructions: Please view this 41-minute lecture for a detailed understanding of the history of Generic Programming in the Java programming language.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

7.3 Commonly Used Classes  

• Reading: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Lists and Sets”

  Link: Hobart and William Smith Colleges: David Eck’s Introduction to Programming Using Java: “Lists and Sets” (PDF)
  
  Instructions: Please read the entirety of this article for a solid introduction to the standard template library and generic programming.  This reading also covers ArrayList and TreeSet concepts.
  
  Terms of Use: The linked material above is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License and can be viewed in its original form here.

  See a broken link? Please let us know!

• Activity: The Saylor Foundation’s “Understanding and Creating TreeSets in Java”

  Link: The Saylor Foundation’s “Understanding and Creating TreeSets in Java” (PDF)
  
  Instructions: Please click on the link above and follow the instructions to complete this activity.  When you have completed this activity, check your answers against The Saylor Foundation’s “Answer Key to Understanding and Creating TreeSets in Java” (PDF).
  
  Completing this activity should take approximately 1 hour.

  See a broken link? Please let us know!

• Activity: The Saylor Foundation’s “Understanding and Creating HashSets in Java”

  Link: The Saylor Foundation’s “Understanding and Creating HashSets in Java” (PDF)
  
  Instructions: Please click on the link above and follow the instructions to complete this activity.  When you have completed this activity, check your answers against the Saylor Foundation’s “Answer Key to Understanding and Creating HashSets in Java” (PDF).
  
  Completing this activity should take approximately 1 hour.

  See a broken link? Please let us know!

7.3.1 Operating on a Collection  

• Reading: University of Hawaii: Edoardo Biagioni’s “Iterators and Linked Lists”

  Link: University of Hawaii: Edoardo Biagioni’s “Iterators and Linked Lists” (HTML)
  
  Instructions: Please read the entirety of this webpage for a solid introduction to linked lists and iterators.  This reading covers the following topics: instantiating a collection with a type, adding elements, accessing elements, iterators, iterator usage, and the comparison between iterator and standard for loop with explicit access.
  
  Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

  See a broken link? Please let us know!

Final Exam  

• Final Exam: The Saylor Foundation’s “CS102 Final Exam”

  Link: The Saylor Foundation’s “CS102 Final Exam”
  
  Instructions: You must be logged into your Saylor Foundation School account in order to access this exam.  If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.

  See a broken link? Please let us know!