Harnessing Technology to make education free

Blog / ePortfolio / Forums / 292 courses / FAQ / digedcon

Elementary Data Structures

Purpose of Course  showclose

When we use programming for problem-solving purposes, data must be stored in certain forms, or Data Structures, so that operations on that data will yield a specific type of output.  Imagine, for example, that a non-profit is having trouble staying afloat and needs an increase in donation.  It decides it wants to keep track of its donors in a program in order to figure out who is contributing and why.  You would first need to define the properties that would define those donors: name, address, amount donated, date of donation, and so on.  Then, when the non-profit wants to determine how to best reach out to their donors, it can create a model of the average donor that contributes to the non-profit—say, for example, based on size of gift and location—so that it can better determine who is most receptive to its mission.  In this case, size of gift and location are the “data” of the donor model.  If the non-profit were to use this model, it would be identifying real donors by first generating an abstract donor.   This is an example of using Abstract Data Types.  Abstract Data Types both take into account the Data Structure (i.e. the way in which data about donors is stored) and provide the necessary operations on that structure.  In this course, we will discuss the theoretical and practical aspects of algorithms and Data Structures.  We will also learn to implement Data Structures and algorithms in C/C++, analyze those algorithms, and consider both their worst-case complexity and practical efficiency.

Course Information  showclose

Welcome to CS201.  Below, please find general information on this course and its requirements.  
 
Course Designer: Bhanu Kapoor
 
Primary Resources: This course is comprised of a range of different free, online materials.  However, the course makes primary use of the following materials:
   
Requirements for Completion: In order to complete this course, you will need to work through each unit and all of its assigned materials.  Pay special attention to unit 1, as this unit will lay the groundwork for understanding the more advanced, exploratory material presented in the later units.  You will also need to complete:
           
            -The Final Exam

Note that you will only receive an official grade on your final exam.  However, in order to adequately prepare for this exam, you will need to work through the materials in each unit.
 
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 approximately 19 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 to determine how much time you have over the next few weeks to complete each unit, and then to set goals for yourself.  For example, unit 1 should take you 13 hours.  Perhaps you can sit down with your calendar and decide to complete subunits 1.1 and 1.2 (a total of 8 hours) on Monday and Tuesday; subunits 1.3 (a total of 5 hours) on Wednesday; etc.
 
Tips/Suggestions: Please follow the directions in each unit of the content outline section to navigate through the course materials.  Please see the prerequisites and required courses in the course requirements section above.  If you are struggling with a concept, it may help to refer back to these courses for a refresher on computer science and discrete mathematics.  It may help to take careful notes as you work through the readings, video lectures, and other resources.  These notes will be useful to study from as you prepare for the final exam.

Learning Outcomes  showclose

Upon successful completion of this course, the student will be able to:
  • Identify elementary Data Structures using C/C++ programming languages.
  • Analyze the importance and use of Abstract Data Types (ADTs).
  • Design and implement elementary Data Structures such as arrays, trees, Stacks, Queues, and Hash Tables.
  • Explain best, average, and worst-cases of an algorithm using Big-O notation.
  • Describe the differences between the use of sequential and binary search algorithms.

Course Requirements  showclose

In order to take this course, you must:

√    Have access to a computer

√    Have continuous broadband internet access

√    Have the ability/permission to install plug-ins or software (e.g. Adobe Reader of Flash)

√    Have the ability to download and save files and documents to a computer

√    Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.)

√    Be competent in the English language

√    Have read the Saylor Student Handbook.

√    Have completed CS101: Introduction to Computer Science I and CS102: Introduction to Computer Science II.

Unit Outline show close


Expand All Resources Collapse All Resources
  • Unit 1: Abstract Data Types and Arrays in C++  

    This unit will introduce students to Abstract Data Types and will make the important distinction between an Abstract Data Type and a Data Structure.  Students will also learn about arrays (a specific type of Data Structure) and the abstracted form of the array data type in C++.

    Unit 1 Time Advisory   show close
    Unit 1 Learning Outcomes   show close
  • 1.1 Abstract Data Types  
  • 1.1.1 Definition of Abstract Data Types  

    This subunit is covered by the “Abstract Data Types” reading assigned at the outset of subunit 1.1 above.  You should read the “Data Abstraction” and “The Definitions in an ADT” sections of the reading to get a good understanding of Abstract Data Types.  An ADT is a mathematical model that captures the problem domain in order to translate it into a program; some examples of ADTs include queues, lists, stacks, trees, graphs, and sets. 

    This reading should take you approximately 20 minutes to complete.

  • 1.1.2 Fundamentals of ADT Implementation  

    This subunit is covered by the “Abstract Data Types” reading assigned at the outset of subunit 1.1 above.  You should read the “Implementation Details” section of the reading to get a good understanding of how one can go about implementing Abstract Data Types.  Since an ADT represents a mathematical model, an implementation of these models makes them accessible to computer programs.  At this point you should think about what data types would be needed and what operations you would be performing on these data types.  All of this is explained in the reading through the use of a class ADT.

    This reading should take you approximately 20 minutes to complete.

  • 1.2 Data Structures  
  • 1.2.1 Contiguous Implementation  
  • 1.2.2 Linked Implementation  
  • 1.2.2.1 The Data and Pointers  
  • 1.2.2.2 Types of Linked Lists  
  • 1.2.2.2.1 Endogenous  

    This subunit is covered by the “Linked List Variations” reading assigned in subunit 1.2.2.2.  You should read the “Endogenous Linked Lists” section of the reading to get a good understanding of endogenous linked lists.  Endogenous linked lists store links within the data.  Typically, most linked lists store links outside of the data.  Endogenous linked lists are useful in system programming tasks.

    This reading should take you approximately 30 minutes to complete.

  • 1.2.2.2.2 Exogenous  

    This subunit is covered by the “Linked List Variations” reading assigned in subunit 1.2.2.2.  You should read the “Doubly-Linked List,” “Cyclic Lists,” and “Dummy Nodes” sections of the reading to get a good understanding of exogenous linked lists.  As we discussed before, most linked lists store links outside of the data; these types of linked lists are called “exogenous” linked lists. In this reading we study doubly-linked lists and cyclic lists as examples of exogenous linked lists.

    This reading should take you approximately 30 minutes to complete.

  • 1.3 Arrays  
    • Reading: CPlusPlus.com’s “Arrays: Lesson I”

      Link: CPlusPlus.com’s “Arrays: Lesson I” (HTML)
       
      Instructions: This reading covers subunit 1.3.1 through 1.3.4 and their respective subunits where applicable.  Please read the information provided in the above link in its entirety.

      This reading should take you approximately 30 minutes to complete.
       
      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: CPlusPlus.com’s “Arrays: Lesson II”

      Link: CPlusPlus.com’s “Arrays: Lesson II” (HTML)
       
      Instructions: This reading covers subunit 1.3.1 through 1.3.4 and their respective subunits, where applicable.  Please read the information provided in the above link in its entirety.

      This reading should take you approximately 30 minutes to complete.
       
      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.1 Elements and Dimension of an Array  

    This subunit is covered by the “Arrays: Lesson I” reading listed in subunit 1.3 above.  You should read the introductory section of the reading to get a good understanding of the elements and dimensions of an array.  An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier.  The number of elements in the array leads to the concept of the dimension of an array, and each item stored in there is an element.  In this subunit we study how to access the elements of an array within the bounds of the dimensions of an array.

    This reading should take you approximately 5 minutes to complete.

  • 1.3.2 Array Basics  

    This subunit is covered by the “Arrays: Lesson I” and “Arrays: Lesson II” readings listed in subunit 1.3 above.  You should read the “Initializing Arrays” and “Accessing the Values of an Array” sections to get a good understanding of basic operations on an array.  Sections 4.1.1, 4.1.2, and 4.1.3 of “Arrays: Lesson II” give you C/C++ examples of array initializations.  At any point of a program in which an array is visible, we can access the value of any of its elements individually as if it were a normal variable, and thus we are able to both read and modify its value.  The reading for this subunit explains this aspect of working with arrays using examples.

    This reading should take you approximately 20 minutes to complete.

  • 1.3.3 Strings as Arrays  

    This subunit is covered by the “Arrays: Lesson II” reading listed in subunit 1.3 above.  You should review the example in “4.1.7: Array of Strings” to get a good understanding of basic operations on an array of strings.  The example shows how to store the days of the week as an array of strings and then access each element of the array of strings just as you would access any other array. 

    This reading should take you approximately 5 minutes to complete.

  • 1.3.4 Multidimensional Arrays  

    This subunit is covered by the “Arrays: Lesson I” reading listed in subunit 1.3 above.  You should read the “Multidimensional Arrays” section of the “Arrays: Lesson I” reading to get a good understanding of basic operations on an array.  Multidimensional arrays can be described as "arrays of arrays."  For example, a two-dimensional array can be thought of as a matrix of elements that are of a uniform data type.  But multidimensional arrays are not limited to two dimensions.  We look into some examples of multidimensional arrays and their implementation in C.

    This reading should take you approximately 5 minutes to complete.

  • Unit 2: Introduction to Stacks and Queues  

    This unit will introduce you to two basic Data Structures—Stacks and Queues—and identify the operations that must be provided with each Stack and Queue implementation.  Students will also learn how arrays and circular arrays can be used to implement a Stack and a Queue and discuss the advantages and disadvantages of their use.

    Unit 2 Time Advisory   show close
    Unit 2 Learning Outcomes   show close
  • 2.1 Introduction to Stacks  
  • 2.1.1 Stack Operations  

    This subunit is covered by the “Stacks” reading listed in subunit 2.1 above.  You should read the article in its entirety to get a good understanding of basic operations on a stack, such as the empty, the push, and the pop.  This subunit is also covered in the first half of the video lecture “Lecture 2: Stacks” listed in subunit 2.1 above.  A stack is characterized by two fundamental operations, called “push” and “pop.”  The push operation adds a new item to the top of the stack, or initializes the stack if it is empty.  The pop operation removes an item from the top of the stack.  We will study how to implement these stack operations.

    This reading should take you approximately 30 minutes to complete.

  • 2.1.2 Stack Elements  

    This subunit is covered by the “Stacks” reading listed in subunit 2.1 above.  You should read the article in its entirety to get a good understanding of elements of a stack that are used in basic operations, such as the empty, the push, and the pop.  This subunit is also covered in the first half of the video lecture “Lecture 2: Stacks” listed in subunit 2.1 above.  Earlier, we looked into abstract data types.  A stack can have any abstract data type as an element.  This subunit covers how the elements of a stack can be implemented and used in the stack operations discussed above.

    This reading should take you approximately 30 minutes to complete.

  • 2.1.3 Stack Construction  

    This subunit is covered in the second half of the video lecture “Lecture 2: Stacks” listed in subunit 2.1 above.  A stack typically has a small number of operations performed on it.  The nature of the pop and push operations mean that stack elements have a natural order.  Elements are removed from the stack in the reverse order to the order of their addition; therefore, the lower elements are those that have been on the stack the longest.  All of these are important aspects of stack construction.

    This reading should take you approximately 30 minutes to complete.

  • 2.2 Array-Based Implementation of a Stack  
  • 2.2.1 Order of Elements Storage in the Array  

    This subunit is covered by the “Stacks: C, C++, and Java Side by Side” reading listed in subunit 2.2 above.  You should read the article in its entirety to get a good understanding of how stacks are implemented in C, C++, and Java programming languages, including the order of elements stored in an array.  Earlier, we covered the elements of a stack.  Here we cover the order of elements of a stack when it is built using an array in programming languages like C++ and Java.

    This reading should take you approximately 30 minutes to complete.

  • 2.2.2 Keeping Track of Array Elements  

    This subunit is covered by the “Stacks: C, C++, and Java Side by Side” reading listed in subunit 2.2 above.  You should read the article in its entirety to get a good understanding of how stacks are implemented in C, C++, and Java programming languages, including how to track elements stored in an array.  Earlier, we covered operations such as push and pop on a stack.  Here we cover how the operations on a stack modify the stack, but we can still keep track of these elements when the stack is built using an array in programming languages like C++ and Java.

    This reading should take you approximately 30 minutes to complete.

  • 2.3 General Presentation of a Queue  
  • 2.3.1 Array Implementation with Periodic Moving  

    This subunit is covered by the “An Introduction to Queues with Examples in C++” reading listed in subunit 2.3 above.  The first few slides cover the array implementation with constant shuffling and periodic moving.  A queue is characterized by fundamental operations such as append, empty, and serve.  Unlike a stack, in a queue, the addition of entities to the rear terminal position and removal of entities from the front terminal position makes it a first-in first-out (FIFO) structure.  This subunit covers how to implement these queue operations using arrays, and with the concept of periodic moving.

    This reading should take you approximately 10 minutes to complete as broken up below.

  • 2.3.2 A Circular Array Manipulation  

    This subunit is covered by the “An Introduction to Queues with Examples in C++” reading listed in subunit 2.3 above.  The last two slides cover the circular array implementation of the queue.  A queue and its operations can also be implemented as a circular array, which we cover in this section.  Like in a stack, the elements of a queue can be constructed using any abstract data type.

    This reading should take you approximately 15 minutes to complete.

  • Unit 3: Pointers and References in C++  

    In this unit, students will cultivate a deeper understanding of how variables are declared and represented in memory.  Students will also learn about pointers and how they can be used to reference certain memory locations.

    Unit 3 Time Advisory   show close
    Unit 3 Learning Outcomes   show close
  • 3.1 Programming Abstractions  
  • 3.2 Pointing to Memory  
    • Reading: CPlusPlus.com’s “Pointers”

      Link: CPlusPlus.com’s “Pointers” (HTML)
       
      Instructions: This reading covers subunit 3.2.  The declaration, use, and dereferencing of pointers is covered in the sections “Reference Operators,” “Dereference Operators,” “Declaring Variables of Pointers Types,” and “Pointers and Arrays” sections of the reading.  A pointer references a location in memory, and obtaining the value at the location a pointer refers to is known as “dereferencing the pointer.”  Several languages support some type of pointer.  Here we look into the fundamentals behind pointing to an item in the memory.
       
      This reading should take you approximately 1 hour to complete.
       
      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 Pointer Arithmetic  
    • Assessment: Cprogramming.com’s “Quiz: Pointers”

      Link: Cprogramming.com’s “Quiz: Pointers” (HTML)
       
      Instructions: Please complete all questions in this quiz.
       
      This assessment should take you approximately 15 minutes to complete, including review for preparation.
       
      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: CPlusPlus.com’s “Pointers”

      Link: CPlusPlus.com’s “Pointers” (HTML)
       
      Instructions: This reading covers subunit 3.3. The pointer arithmetic involving adding a number to a pointer variable, and adding a number to a dereferenced pointer array, are covered in the “Pointer Initialization,” “Pointer Arithmetic,” and “Pointers to Pointers” sections of the reading.  When you are pointing to something in memory, you need to be able to continue to point to the right item depending on the need for computation.  This requires advancing pointers and taking steps back if needed.  All of this needs pointer arithmetic.  Knowledge of pointer arithmetic separates those who passably know C from those who know C really well.  It's said that a good programmer understands pointers very well, while an average programmer finds anything with more than one pointer difficult to manage.  This unit will help you make progress towards becoming a good programmer.
       
      This reading should take you approximately 1 hour to complete.
       
      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: Dynamic Memory Allocation  

    We will now learn about dynamic memory allocation.  Frequently, we know neither the size of the data nor the Data Structure when implementing programs and Data Structures.  By learning about dynamic memory allocation, students will understand how to request memory during runtime.  We will also discuss the risks of memory allocation and de-allocation, learning about memory leaks and dangling pointers, among other potential drawbacks.  Students will learn how to prevent these risks by utilizing the full capabilities of the C/C++ language to increase memory use efficiency.

    Unit 4 Time Advisory   show close
    Unit 4 Learning Outcomes   show close
  • 4.1 Static versus Dynamic Memory Allocation  

    The first two slides of the reading address the differences between static and dynamic allocations and discuss what a memory heap is, the need for references, and the new operator.

    This reading should take you approximately 5 minutes to complete.

  • 4.2 Pointing to Memory Allocation at Run Time  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  Until now, in all our programs, we have only had as much memory available as we declared for our variables, with the size of all of them to be determined in the source code, before the execution of the program.  But what if we need a variable amount of memory that can only be determined during runtime, for example, a case in which we need some user input to determine the necessary amount of memory space?

    This reading should take you approximately 45 minutes to complete.

  • 4.3 Using Memory Allocated at Run Time  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  Here we look into how we use pointers in working with the memory allocated at runtime.

    This reading should take you approximately 45 minutes complete.

  • 4.4 Run Time Allocation of Arrays  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  In order to request dynamic memory we use the operator new, which is followed by a data type specifier and—if a sequence of more than one element is required—the number of these within brackets [ ].  It returns a pointer to the beginning of the new block of memory allocated.

    This reading should take you approximately 45 minutes to complete.

  • 4.5 Returning Memory to the Heap  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  Most applications request memory from the heap when they are running.  It is possible to run out of memory (you may even have gotten a message like "Running Low On Virtual Memory") when running a program.  So, it is important to return memory to the heap when you no longer need it.

    This reading should take you approximately 45 minutes to complete.

  • 4.6 Memory Leaks  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  Memory leaks when it is allocated from the heap using the new operator but not returned to the heap using the delete operator.

    This reading should take you approximately 45 minutes to complete.

  • 4.7 Dynamic Memory Allocation for Objects  

    This subunit is covered by the “Dynamic Memory Allocation in C++ - An Introduction” reading listed in subunit 4.1 above.  We can dynamically allocate memory for objects, which the last section of the reading covers in some detail.

    This reading should take you approximately 45 minutes to complete.

  • Unit 5: Linked Stacks, Queues, and Lists  

    This unit will introduce students to three new types of Data Structures: Linked Stacks, Queues, and lists.  We will discuss their respective operations and learn how the use of node classes and pointers can provide us with a means of implementing them. 

    Unit 5 Time Advisory   show close
    Unit 5 Learning Outcomes   show close
  • 5.1 Nodes in Linked Stacks and Queues  
  • 5.2 Linked Queues  
    • Reading: Oracle Think Quest Education Foundation’s “Queues”

      Link: Oracle Think Quest Education Foundation’s “Queues” (HTML)
       
      Instructions: This reading covers the empty method, the append methods, the server methods, and the private attributes associated with linked queues.  Please read this webpage in its entirety.  The web page provides information about Linked Queues as a Class with examples in C++.

      This reading should take you approximately 15 minutes to complete.
       
      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.3 Lists with Arrays  
    • Reading: FunctionX Inc.’s “Creating Linked Lists with Arrays”

      Link: FunctionX Inc.’s “Creating Linked Lists with Arrays” (HTML)

      Instructions: Please read the linked page in its entirety; the author provides information about creating linked lists with arrays using examples from C++.  You will learn about the fixed size implementation, the overhead in shuffling, and implementation of a list with nodes as a class.

      This reading should take you approximately 30 minutes to complete.
       
      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: Algorithm Efficiency  

    There are a number of parameters that developers must consider when designing Data Structures.  One of the most important parameters relates to the efficiency of the algorithms (i.e. searching algorithms) that can be used on the Data Structures.  This unit will explain how to measure an algorithm’s efficiency, identify problems that arise when taking these measurements, and present ways of representing algorithm efficiency.

    Unit 6 Time Advisory   show close
    Unit 6 Learning Outcomes   show close
  • 6.1 Algorithm Efficiency Measurements  
  • 6.2 Bounds  
  • 6.3 Comparing Algorithms  
  • 6.4 Determining Asymptotic Bounds  
  • Unit 7: Searching and Sorting Algorithms  

    In this unit, students will learn to apply searching and sorting algorithms to arrays.  Students will also learn how to conduct worst-case and best-case analysis for these algorithms, determine their efficiency, and assign them generalized Big O notations.

    Unit 7 Time Advisory   show close
    Unit 7 Learning Outcomes   show close
  • 7.1 Searching Arrays  
    • Web Media: YouTube: XoaX.net’s “Linear and Binary Searching”

      Link: YouTube: Xoax.net’s “Linear & Binary Searching” (YouTube)
       
      Instructions: This video covers linear and binary search.  In linear search, we discuss a worst-case target at the end of the array and derive the efficiency of the algorithm.  We also look into the efficiency of the binary search algorithm.  Please watch the video in its entirety.  You only need to watch the video; you can disregard the remainder of the text on the page.  The video provides general information about Linear and Binary Search using examples from C++.

      This lecture should take you approximately 10 minutes to complete.
       
      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 Bubble Sorts for Arrays  
    • Web Media: Youtube: XoaX.net’s “Bubble Sort”

      Link: YouTube: Xoax.net’s “Bubble Sort” (YouTube)
       
      Instructions: This video covers subunits 7.2.1 and 7.2.2.  Please watch the video in its entirety.  You only need to watch the video; you can disregard the remainder of the text on the page.  This video provides general information about bubble sort with examples in C++.

      This lecture should take you approximately 5 minutes to complete.

      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.1 The Process and Implementation in C++  

    This subunit is covered in the first half of the video lecture “Bubble Sort” listed in subunit 7.2 above, where we look into the process associated with the implementation of the bubble sort algorithm in C++.  Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order.  The algorithm gets its name from the way smaller elements "bubble" to the top of the list.

    This part of the lecture should take you approximately 2 minutes to complete. 

  • 7.2.2 Efficiency Analysis  

    This subunit is covered in the second half of the video lecture “Bubble Sort” listed in subunit 7.2 above, where we look into the number of inner and outer iterations, the worst-case running time, and the associated Big-O notation for the algorithm. 

    This part of the lecture should take you approximately 2 minutes to complete. 

  • 7.3 Insertion Sorts for Arrays  
    • Web Media: YouTube: XoaX.net’s “Insertion Sort”

      Link: YouTube: Xoax.net’s “Insertion Sort” (YouTube)
       
      Instructions: This video covers subunits 7.3.1 and 7.3.2.  Please watch the video in its entirety.  You only need to watch the video; you can disregard the remainder of the text on the page.  The web site provides general information about insertion sort with examples in C++.

      This lecture should take you approximately 5 minutes to complete.
       
      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.1 The Process and the Implementation in C++  

    This subunit is covered in the first half of the video lecture “Insertion Sort” listed in subunit 7.3 above, where we look into the process associated with the implementation of the insertion sort algorithm in C++.  Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.  It is not the most efficient sorting algorithm, but it has a simple implementation and is quite efficient for small data sets.

    This part of the lecture should take you approximately 2 minutes to complete.

  • 7.3.2 Efficiency Analysis  

    This subunit is covered in the second half of the video lecture “Insertion Sort” listed in subunit 7.3 above, where we look into the number iterations, the worst-case running time, and the associated Big-O notation for the algorithm.

    This part of the lecture should take you approximately 2 minutes to complete.

  • 7.4 Selection Sorts for Arrays  
    • Reading: Algolist.net’s “Selection Sort”

      Link: Algolist.net’s “Selection Sort” (HTML)
       
      Instructions: This reading covers subunits 7.4.1 and 7.4.2.  Please read the linked page in its entirety for information about selection sort, using examples in C++.

      This reading should take you approximately 10 minutes to complete.
       
      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.4.1 The Process and the Implementation in C++  

    This subunit is covered in the first half of the video lecture “Selection Sort” listed in subunit 7.4 above, where we look into the process associated with the implementation of the selection sort algorithm in C++.  Selection sort works by first finding the smallest in the array and exchanging it with the element in the first position, then finding the second smallest element and exchanging it with the element in the second position, and continues in this way until the entire array is sorted.

    This part of the lecture should take you approximately 5 minutes to complete.

  • 7.4.2 Efficiency Analysis  

    This subunit is covered in the second half of the video lecture “Selection Sort” listed in subunit 7.4 above, where we look into the number of iterations, the worst-case running time, and the associated Big-O notation for the algorithm.  Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array.  It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.  Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

    This part of the lecture should take you approximately 5 minutes to complete.

  • 7.5 Merge Sorts for Arrays  
    • Web Media: YouTube: XoaX.net’s: “Merge Sort”

      Link: YouTube: Xoax.net’s: “Merge Sort” (YouTube)
       
      Instructions: This video covers subunits 7.5.1 and 7.5.2.  Please watch the video in its entirety.  You only need to watch the video; you can disregard the remainder of the text on the page.   Please read the linked page in its entirety for information on merge sort using examples in C++.

      This lecture should take you approximately 5 minutes to complete.
       
      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.5.1 The Process and the Implementation in C++  

    This subunit is covered in the first half of the video lecture “Merge Sort” listed in subunit 7.5 above, where we look into the process associated with the implementation of the merge sort algorithm in C++.  Merge sort is a divide-and-conquer approach in which you produce a single sequence of items ordered according to some rule, from two or more previously ordered or unordered sequences, without changing the items’ size, structure, or total number.  Although more than one pass may be required for a complete sort, items are selected during each pass on the basis of the entire key.

    This part of the lecture should take you approximately 2 minutes to complete.

  • 7.5.2 Efficiency Analysis  

    This subunit is covered in the second half of the video lecture “Merge Sort” listed in subunit 7.5 above, where we look into the number of inner and outer iterations, the worst-case running time, and the associated Big-O notation for the algorithm.  Merge sort is an O(n log n) comparison-basedsorting algorithm.  Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

    This part of the lecture should take you approximately 2 minutes to complete.

  • Unit 8: Hash Tables, Graphs, and Trees  

    This unit will identify various problems that computer scientists encounter when using array indexes and present Hash Tables as a solution.  Students will learn about different Hash Tables categories, identifying their respective performance efficiencies.  The unit will conclude with an introduction to graphs and special graph types known as trees and binary trees.  We will learn how to implement these new Data Structures, discuss operations that accompany them, and identify different ways of traversing, searching, and sorting them.

    Unit 8 Time Advisory   show close
    Unit 8 Learning Outcomes   show close
  • 8.1 Categories of Hash Functions, Linear Probing, and Chaining  
    • Lecture: YouTube: University of California–Berkeley: Professor Johnathan Shewchuk’s "Lecture 21: Hash Tables”

      Link: YouTube: University of California–Berkeley: Professor Johnathan Shewchuk’s "Lecture 21: Hash Tables” (YouTube)

      Instructions: This video covers hash table data structure.  The first part of the video covers the types of hash functions, collisions, and the idea of chaining to deal with collisions.  Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys.  For example, if 2,500 keys are hashed into a million buckets, even with a perfectly uniform random distribution, according to the birthday problem there is a 95% chance of at least two of the keys being hashed to the same slot.  Therefore, most hash table implementations have some collision-resolution strategy to handle such events.  Some common strategies are described below.  This has led to the ideas of linear probing and chaining.
       
      This part of the lecture should take you approximately 30 minutes to complete.

      Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

      See a broken link? Please let us know!

  • 8.2 The Efficiency and Performance of Hash Tables  
  • 8.3 Graphs  
    • Lecture: YouTube: University of California – Berkeley: Professor Shewchuck’s “Data Structures: Topic Graphs”

      Link: YouTube: University of California – Berkeley: Professor Shewchuck’s “Data Structures Topic Graphs” (YouTube)
       
      Instructions: This lecture covers simple graphs, vertices, edges, and links.  It discusses the idea of paths in graphs.  Several graph types, including directed and undirected, are discussed.  After that, the lecture covers data structures such as the adjacency matrix, adjacency list, and hash-table based implementations of graphs.  To access the video, click on the above link.   

      This part of the lecture should take you approximately 1 hour to complete.
       
      Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.

      See a broken link? Please let us know!

  • 8.4 Additional Graph Concepts: Walk, Trail, Path, and Circuits  
  • 8.5 Binary Search Trees (BST)  
  • Final Exam  

« Previous Unit Next Unit » Back to Top