Code Complete by Steve McConnell : Chapter 8

The author recommends defining major data structures during requirements analysis and architecture phase.

The author then provides a data literacy test to identify what expertise the reader posses in understanding data structures. He also recommends reading some books if the reader is not an expert in data structures.

The author then enlists reasons to create own data types:

• Make modifications easier in future
• Avoid excessive information distribution
• Increase Reliability
• Compensate for language weaknesses
  

The author then provides guidelines for creating own data types:

• Create types with problem domain names
• Do not use predefined types (like int, float in C++) directly in the code except in type definitions
  
• Never redefine predefined types since it can create confusion in the mind of reader
• Define substitute types for portability
• Create types using other created types

The author then provides some guidelines for variable declarations:

• Use a template for variable declaration
• Turn of implicit declarations
• Use naming conventions

The author emphasizes the importance of data initialization. Improper initialization can result from several situations:

• A variable is never initialized
• A variable's value is outdated
• Only a part of the variable is assigned a value
  

The author then provides some guidelines for data initializations:

• Check input parameters for validity
• Initialize each variable close to where it is used
• Check the need for reinitialization
• Initialize named constants once, initialize variables with executable code
• Initialize each variable as it's declared
• Use compiler setting to initialize all variables
• Use compiler warnings for uninitialized variables
• Use a memory access checker to check for bad pointers
• Initialize working memory at the beginning of the program
  

Code Complete by Steve McConnell : Chapter 7

The author defines software design as a scheme of turning a specification of a computer program into an operational program. Design links requirements specification to coding and debugging. The author points out that design is a heuristic process and requires creativity and insight.

The author tries to distinguish between designs done in large and small projects. In large projects, design might be an activity distinct from requirements and coding and carried out by different set of people. The design may be divided in several stages like software architecture, high-level module design and detailed implementation design. Design work continues even after the design phase is over.

On small projects, design might involve just writing the PDL before coding it in the programming language.

The author then discusses design at different levels:

• Division into subsystems: This involves identification of major components in the software and interfaces/interaction between them.
  
• Division into modules: If a subsystem is too big to translate to module, this level ensures that the subsystem has been decomposed to a level of detail fine enough to implement it as a set of modules.
• Division into routines: This involves dividing a module into service routines and specifying syntactic details of service routines.
• Internal routine design: This requires writing PDL, investigating algorithms, deciding on organization of code and then coding in programming language.
  

The author then discusses two approaches of structured design:

• Top Down Decomposition: It is also called top-down design or stepwise refinement. It involves moving from a general statement of what the program does to detailed statements about specific tasks that are performed. Following steps should be followed in top down decomposition:
  
• Design top levels first before moving to lower levels
• Avoid language specific details
• Postpone details to lower level design
• Formalize and Verify each level
• Move to next level for next set of refinement

The author compares the technique with divide and conquer. The author advises to continue decomposition until it seems it is easier to code then decompose.

• Bottom Up Composition: Following steps need to be followed in bottom up decomposition:
• Identify low level capabilities from the description of the problem
• Identify common aspects of low level capabilities and group them
• Continue with the next level up

The author enlists following strengths of top-down approach:

1. It is easy
2. Implementation details can be deferred

Following weaknesses are also mentioned:

1. Systems not hierarchical in nature are difficult to design using this approach
2. This approach requires single function at the top which is different from modern event driven systems
3. Top level function of a system is hard to identify

The author provides following strengths of bottom-up approach:

1. It identifies utility routines early which results in compact design
2. It results in a lot of reuse

The following weaknesses of the bottom-up approach are mentioned:

1. This approach cannot be used exclusively. It needs to be combined with top-down approach.
2. Sometimes it becomes difficult to assemble pieces to build the system.
   

The author then discusses object-oriented design. The author defines the object-oriented design process as identification of real-world and abstract objects and representation of this objects by programming language objects. The author clarifies that object-oriented design works at a higher level of abstraction than structured design and the building of design is based on the data which makes it more stable approach.

The author then discusses following ideas related to object-oriented programming:

1. Abstraction: Object oriented design allows to ignore irrelevant details.
   The unit of abstraction in structured design is a function while in object-oriented design; it is an object. Since object has both functions and data, object-oriented design provides bigger intellectual building blocks than structured design.
   
2. Encapsulation: It involves principles of information hiding.
   
3. Modularity: It is nothing but grouping of related services and data into modules that are highly cohesive and loosely coupled.
   
4. Hierarchy and Inheritance: This involves identifying similarities and differences between different objects.
   
5. Objects and classes
   

The author provides following steps for object-oriented design:

• Identify objects and their attributes
• Determine what can be done to each object
• Determine what each object can do to other objects
• Determine parts of each object that will be visible
• Define each object's public interface
  

The author classifies objects in four main categories:

1. Problem Domain Component
2. User Interface Component
3. Task Management Component
4. Data Management Component
   

The author points out that without some object in each of these categories makes an incomplete design.

The author then compares following popular design approaches:

1. Structured Design: It works well for systems with several hundred lines of code.
   
2. Information Hiding: This approach should be used whenever possible.
   
3. Object Oriented Design: It works well for systems with more than hundred thousand to over a million lines of code.
   

The author suggests not to restrict to using only one approach. The author points out following three traits of the design process:

• Design is a sloppy process
  
• Design is a wicked problem
• Design is a heuristic process: The author provides reference to G Polya's book, How to Solve It and summarizes the approach that he suggested in his book.
  

When the design gets complete, it should have following characteristics:

1. Intellectual Manageability
2. Low Complexity
3. Ease of Maintenance
4. Minimal Connectedness
5. Extensibility
6. Reusability
7. High fan-in
8. Low to medium fan-out
9. Portability
10. Leannes
11. Stratified Design
12. Standard Techniques
    

Find depth of a k-ary tree given a parent array : Solution 1

The problem statement is mentioned here.

Following is the first solution.

initialize maxDepth to 0
for each node i from 0 to N-1
    set parent to P[i]
    set depth to 1
    while parent is not -1
       set parent to P[parent]
       increment depth
    end while
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N^2)$ where $N$ is the number of nodes. The space complexity is $O(1)$.