CSC2025 Quiz 4

Fall 2013
Herbert J. Bernstein ( )

CSC2025 Quiz 4
Fall 2013

 		 

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC2025F13/CSC2025_Quiz_4.html
Copyright © 2004, 2011, 2013 Herbert J. Bernstein and other parties. All rights reserved.

This is the fourth daily quiz to be taken on or before 15 October 2013. Please do this quiz after you have completed the rest of asignment 4. It should take between one half hour and 2 1/2 hours to complete if you are well prepared, longer if not.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:

Name:


Email:

Skype ID:

Please answer the following questions on this form (or on a paper copy of this form).

  1. Explain how to transfer a program or other file from your computer to your web site on Google Sites.

  2. Define a list, explaining both what one stores in a list and what operations you need to be able to perform on a list. For each operation provide a time and space estimate using big O notation assuming use of a linked list implementation.

  3. Redo the time estimates of question 2, assuming a Vector class implementation of a list, rather than a linked list implementation.

  4. Define a stack, explaining both what one stores in a stack and what operations you need to be able to perform on a stack. For each operation provide a time and space estimate using big O notation assuming use of an array implementation.

  5. Define a queue, explaining both what one stores in a queue and what operations you need to be able to perform on a queue. For each operation provide a time and space estimate using big O notation assuming use of an array implementation.

  6. Explain what would be similar and what would be different in designing a linked list to be stored in memory versus a linked list to be stored on disk.

  7. Using any suitable programming language, write the a method or function (not a program) to merge two sorted of integers lists into one sorted list of integers. You are to use a linked list as your data structure. Then write a program and test data that will test your method or function. You are to do the linked list implementation, not use an existing class.

  8. Using any suitable programming language, write a method or function to search a large string of text for the presence of a particular short string of text. In the comments of the program discuss the choices of data structures to use. Then write a program and test data that will test your method or function. You are to do your own implementation, not use an existing class.

  9. Carefully and in detail describe the data structures you would use to make a program to play tic-tac-toe.

  10. Explain the three most important things you learned from Dr. Garg's lecture 16.

  11. Explain the three most important things you learned from Dr. Garg's lecture 17.

  12. Explain the three most important things you learned from Dr. Garg's lecture 18.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 13 October 2013