Intro to Problem solving via Computers

In collaboration with Nadine Ferguson, the following questions were compiled to initiate a book on learning programming and problem-solving via computers, by asking questions:

By asking questions, real-world examples, and multiple solutions to the same problem.

Questions

1. What is the problem?

2. What is a solution?

3. What is an efficient solution?

4. What is a computer?

5. How can a solution be communicated to computers?

6. What is an algorithm and how does it help in programming computers?

7. What is abstraction? Could you explain with examples?

8. What are the Turing primitives?

9. What is a flowchart?

10. What are ANSI Standard symbols for drawing a flowchart?

11. Draw parallels between the flowchart symbols and Turing primitives.

12. What is a program, and how can we translate a flowchart or algorithm into a computer program?

13. What is a computer language? Why do we need a language or multiple languages?

14. What is Python, what paradigms is it developed in, and what does it support?

15. What is the Object-Oriented Programming paradigm? Compare the same with alternative paradigms.

16. What are some examples of Python objects?

17. What is an error? How many types of errors do you think can occur? 

18. Can you relate computer program errors to people's mistakes in learning natural languages such as English?

19. Which error poses the least difficulty and removal?

20. Which error poses the most difficulty and removal?

21. How can you tell if a program is correct, i.e., will correctly solve the problem it is intended to?

22. How do we ensure a mathematical predicate/statement/solution is correct?

23. What is proof? How can we prove that a program will always work?

24. What are testing (automated testing using doctest) and debugging?

25. What are the major types of testing-- Unit and integration testing?

26. What are the basic building blocks of a computer?

27. How many ways can a program receive input?

28. How many ways a program can output?

29. What is memory?

30. What number system(s) do computers understand?

31. What is the binary number system?

32. What happens when you press a key on the keyboard?

33. What is an ASCII table? What it is used for?

34. Write down ASCII values for letters a-z, A-Z, and digits 0-9

35. What are variables/names? What are values?

36. How many types of values a variable can hold?

37. What are the common built-in data types in Python?

38. What is static and dynamic typing? Which one would be slower?

39. What is Scope in Python?

40. What is Scope Resolution in Python?

41. What types of operators are allowed in Python? Explain operators for each data type.

42. Can you explain the ternary operator in Python?

43. What is an assignment?

44. Mutability (in-place change) and Rebinding (associated with another value)

45. What is a function (mathematical definition)?

46. What is a function in computer programming?

47. What are the arguments and parameters?

48. Explain arguments, default arguments, and keyword arguments.

49. What is a return value and what gets returned without a return statement?

50. What are the built-in functions in Python (e.g., print, range)

51. Draw an equivalence between Turing primitives, flowchart boxes, and programming constructs.

52. What are the minimum things we need to communicate to the computer? What are the advantages?

53. What is the control flow?

54. What are conditionals?

55. Can we chain conditionals?

56. Can we nest conditionals?

57. What are loops?

58. Nested loops? Why do we need it?

59. How to break a loop?

60. How do you replace a break statement in a loop with a Boolean flag?

61. What is break, continue, and pass in Python?

62. What is an infinite loop? Could you explain a scenario in which it is inevitable?

63. What are collections? What types are available in Python to hold a collection of values?

64. What are lists?

65. What are negative indexes, and why are they used? Explain at least 4 situations in which negative indices are handy.

66. What types of operations can be performed on a collection, such as lists?

67. Traversing a list, modifying a list, creating a list from another list

68. How do you copy an object in Python? How to copy a list into another list?

69. What are deep copy and shallow copy in Python? Provide an example for data types where deep and shallow copy applies.

70. What is the difference between Python Arrays and lists?

71. Multi-dimensional lists. Matrix operations (addition, subtraction, multiplication, transpose)

72. How do you traverse a 2D matrix?

73. How do you transpose a 2D matrix?

74. How do you find the sum of the principal diagonal elements in a 2D matrix?

75. What are strings? How is it different from the list?

76. What operations can be performed on strings?

77. How will you search for a string in a big string?

78. Implement the Caesar Cipher encryption algorithm using string methods

79. What are the string-matching algorithms?

80. Can you print the sum of the squares of digits of a number?

81. What are mutation and rebinding, and how does it apply to lists and strings?

82. What are tuples? What are the usages of tuples in programming situations?

83. What are dictionaries? What are they useful for?

84. How to work with a collection of elements?

85. Loops and collections (list, tuple, dictionaries)

86. Collection of collections?  (list of lists, tuples, dictionaries; tuple of lists, tuples, dictionaries, etc.)

87. Provide some examples that use both lists and dictionaries.

88. Provide some examples that use lists and tuples

89. Provide some examples that use tuples and dictionaries

90. What are Dict and List comprehensions?

91. What data structure/type can be used in Python to store unique data and eliminate duplicate items?

92. How do you find the intersection of two sets?

93. How do you find the union of two sets?

94. How do you find the difference between the two sets?

95. How do you find the symmetric difference between the two sets?

96. How do you find subsets and supersets?

97. What is the lambda function in Python? Why is it used?

98. What is a flag variable, and what scenarios do we need it?

99. What are modules and packages in Python?

100. Differentiate between a package and a module in Python.

101. What are some of the most commonly used built-in modules in Python?

102. How do you generate random numbers in Python?

103. Write a Python program to simulate virtual dice.

104. How do you create 100 random integers in a specified range in Python?

105. How to generate a floating-point number in a range specified by the user?

106. How do you select a random element from a list?

107. What is persistence?

108. How to read from a file?

109. How do you write to a file stored on a hard disk?

110. How do you append data to an existing text file?

111.  What is a read position/file pointer, and how can you reset it for multiple file reads?

112. How to read a file one line at a time?

113. How do you read a text file into a list?

114. Can a file object be iterated over to process a text file line by line?

115. How to read and write numeric data from/write to a file?

116. How to process data written to a file as records and fields?

117. What is exception handling? And how do you catch exceptions in Python?

118. How can you use exception handling in file I/O to check for file existence?

119. What is the difference between run-time errors and semantic errors?  

120. What are files? What is a directory? How to get the current working directory in Python?

121. How do I get a list of all the files in a directory?

122. What are the resources a program consumes?

123. How do we measure the amount of space a program takes? What is unit do we use?

124. How do we measure the amount of time a program takes? What is the unit that we use?

125. What are the factors that impact a program's running time? Is it possible to keep track of all these factors? Do you think these factors are stable, and can we rely on their time?

126. Does the number or amount of resources a program takes depend on the programming language that we use?

127. Is there a way to measure the resources a program consumes independent of programming language?

128. What are algorithms?

129. Does an algorithm always take the same steps to solve a problem?

130. Does input affect the time taken by an algorithm?

131. What is the best case, worst case, and average case in the complexity analysis of an algorithm?

132. What are the notations used to indicate the best, worst, and average-case complexities?

133. Why do we always do the worst-case complexity analysis of algorithms?

134. What do you understand about algorithmic complexity?

135. What is the order of growth?

136. What is the major family of functions that we use to indicate the order of growth of an algorithm?

137. Can you put those functions listed in Q. 110 in order of their growth?

138. How do we measure algorithmic complexity?

139. How do we measure the complexity of algorithms that exclusively use loops? Could you explain with examples?

140. Is there an alternative for loops?

141. Could you explain the divide and conquer strategy to solve a problem?

142. What is recursion?

143. How do you define the base case?

144. What are the characteristics of the general case for recursion?

145. How do you avoid infinite recursion?

146. How is recursion different from iteration?

147. Define a recursive function to calculate the factorial of a number.

148. Define a function that recursively counts down from a user-inputted integer.

149. Describe the flow of execution of a recursive function.

150. What is one-way vs. two-way recursion?

151. Could you draw the call stack diagram for a two-way recursive function?

152. What does it mean when a Python program generates a “maximum recursion depth exceeded” error?

153. Define a linear search function in Python.

154. Write the algorithm for binary search and implement it in Python.

155. Write the algorithm for bubble sort and implement it in Python

156. How do you implement a quicksort algorithm in Python?

157. How to implement a linear search using recursion?

158. What is the best, worst, and the average case for linear search?

159. How to implement a binary search in recursion?

160. What is the best, worst, and the average case for binary search?

161. How to check if a string is a palindrome?

162. How to compute factorial using a loop?

163. How to compute factorial using recursion?

164. How to find the sum of a given list of numbers using a loop?

165. How would you compute the sum of a list of numbers using recursion?

166. How to compute nth Fibonacci using a loop?

167. How to compute nth Fibonacci using recursion?

168. How to measure the complexity of algorithms that exclusively use recursion (or divide and conquer strategy) to solve a problem?

169. What is a recurrence relation?

170. What is the master’s theorem?

171. What kind of algorithms can be analyzed using the master’s theorem?

172. What is the runtime complexity of searching an element in an unsorted list of elements?

173. What is the runtime complexity of searching an element in a sorted list of elements?

174. What is the cost of maintaining a sorted list?

175. Is maintaining a sorted list and searching in O(log n) possible? How?

176. What are ADTs?

177. Describe a stack ADT and how objects are accessible in a stack

178. Implement a stack/LIFO using list push and pop operations. How would you determine the number of objects in a stack? Add an element to the top of the stack. Remove the top item on the stack.

179. Describe the performance characteristics of a well-designed stack in terms of algorithm complexity (big O notation). What is the cost of a pop and push stack operation?

180. What other Python data structure can be used to implement a stack?

181. How would you implement a queue/FIFO structure in Python?

182. What ADT is used if the object needs to be inserted in the middle of the sequence (instead of the start or end)?

183. What is a linked list?

184. Write a program to traverse a linked list and delete the first and last nodes.

185. What is the difference between a singly linked list and a double linked list? Could you give an example? When would you use each?

186. What is a non-linear data structure? What are the heavily studied non-linear data structures?

187. What is a tree?

188. What is a rooted tree?

189. What is an ordered tree?

190. What is a search tree?

191. What is a binary search tree (BST)?

192. What are the ways to represent a binary search tree in a computer?

193. What are the problems with an array-based representation of a BST?

194. Why is a linked-list-based structure an efficient way of representing a BST?

195. How to insert an element in a BST?

196. What is the complexity of the insertion process in the best and worst cases?

197. How to search for an element in a BST?

198. What is the complexity of the search process in the best and worst cases?

199. How to delete an element from a BST?

200. What is the complexity of the deletion process in the best and worst cases?

201. What is a balanced BST?

202. What would be the complexity of keeping a BST balanced?

203. What is hashing?

204. What is a collision in hashing?

205. What is chaining?

206. What is the complexity of searching an element in a hash table?

207. How would you search for the occurrence of a string in a text?

208. What would be the computational complexity of finding a fixed string in a text?

209. Is there a way to improve the computational complexity of the string-matching process?