The paper-and-pencil programming strategy (PPS) is a way of representing an idea logically by any representation that can be created using paper and pencil. It was developed for non-computer majors to improve their understanding and use of computational thinking and increase interest in learning computer science. A total of 110 non-majors in their sophomore year were assigned to either a Logo or a PPS course with attendance being 2 hours per week for 15 weeks. To measure the effectiveness of PPS, the Group Assessment of Logical Thinking and a self-assessment survey pre- and post-test were used. Findings indicated that PPS not only improved students' overall logical thinking as much as did Logo programming learning, but also increased scores on one more subscale of logical thinking than did the Logo course. In addition, PPS significantly helped students understand the concept of computational thinking and increased their interest in learning computer science.