Sachverhalt: A. A.a. Y._ und X._ sind die gemeinsamen nicht verheirateten Eltern der am 16. Juli 2009 geborenen Tochter A._. Die von den Eltern am 22. Juni 2010 geschlossene Vereinbarung über den Unterhalt und die Betreuung des gemeinsamen Kindes sah insbesondere vor, dass dieses von beiden Eltern zu gleichen Teilen je zweieinhalb Tage pro fünf Werktage plus Samstag oder Sonntag bzw. plus jedes zweite Wochenende betreut wird, wobei diese Betreuungsregelung auch bei einer eventuellen Auflösung des gemeinsamen Haushaltes (Pendelmodell) gelten soll. Am 9. August 2010 genehmigte die Vormundschaftsbehörde B._ die Vereinbarung und übertrug gestützt auf aArt. 298a Abs. 1 ZGB die elterliche Sorge über das Kind antragsgemäss auf beide Eltern. A.b. Im Juni 2011 trennten sich die Eltern und leben seither nicht mehr im gemeinsamen Haushalt. Die Mutter zog nach Basel. Am 15. Juni 2012 änderte die Vormundschaftsbehörde Basel-Stadt nach Anhörung des Sozialarbeiters und der Eltern die Betreuungsregelung dahingehend, dass das Kind wöchentlich alternierend zwei und in der darauffolgenden Woche drei Tage (mit Übernachtungen; beispielsweise von Donnerstag, 09.30 Uhr, bis Freitag, 18.00 Uhr, und in der jeweils darauffolgenden Woche von Donnerstag, 09.30 Uhr, bis Sonntag, 18.00 Uhr) beim Vater verbringt (Ziff. 1). Vorgesehen wurde ferner, dass das Kind nach vier Monaten wöchentlich alternierend zwei Tage und in der jeweils darauf folgenden Woche vier Tage beim Vater verbringt (beispielsweise von Donnerstag, 09.30 Uhr, bis Freitag 18.00 Uhr und in der folgenden Woche von Donnerstag, 09.30 Uhr, bis Sonntag, 18.00 Uhr (Ziff. 2). Nach Ablauf von vier Monaten gilt die bestehende Ferienregelung, wonach beide Elternteile gleich viel Ferien mit dem Kind verbringen dürfen. B. Der Vater gelangte gegen den Beschluss der Vormundschaftsbehörde mit Rekurs an das Verwaltungsgericht des Kantons Basel-Stadt mit den Begehren, die Ziffern 1 bis 3 des angefochtenen Beschlusses aufzuheben und neu zu bestimmen, dass die Tochter wöchentlich alternierend 3 Tage inkl. 2 Übernachtungen, in der darauffolgenden Woche 4 Tage inkl. 3 Übernachtungen bei ihm verbringe. Ferner sei festzustellen, dass nach Ablauf der Übergangszeit die Kontaktregelung gemäss Vereinbarung vom 22. Juni 2010 gelte. Mit Urteil vom 20. Dezember 2012 wies das Appellationsgericht Basel-Stadt als Verwaltungsgericht den Rekurs ab. C. Der Vater (Beschwerdeführer) gelangt mit Beschwerde in Zivilsachen vom 13. März 2013 (Postaufgabe) an das Bundesgericht. Er beantragt sinngemäss, das angefochtene Urteil des Verwaltungsgerichts sei insofern abzuändern, als nach Ablauf der Übergangszeit die bestehende Kontaktregelung gemäss Vereinbarung vom 22. Juni 2010 gelte. Für das bundesgerichtliche Verfahren ersucht er um unentgeltliche Rechtspflege. Mit Eingabe vom 11. Juni 2013 wurde die Beschwerde korrigiert. D. Das Appellationsgericht Basel-Stadt hat sich am 10. Juni 2013 vernehmen lassen. Die Mutter (Beschwerdegegnerin) hat am 24. Juni 2013 zur Beschwerde Stellung genommen. Sie beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Ferner ersucht sie um Gewährung der unentgeltlichen Rechtspflege und um Sicherstellung ihrer Parteikosten. Der Beschwerdeführer hat sich am 9. Juli 2013 zur Vernehmlassung der Vorinstanz und der Beschwerdegegnerin geäussert. Das Appellationsgericht hat am 15. Juli 2013 auf eine weitere Stellungnahme verzichtet. Die Beschwerdegegnerin hat am 30. August 2013 zur Eingabe des Beschwerdeführers vom 9. Juli 2013 Stellung genommen, worauf der Beschwerdeführer am 7. September 2013 sich zum Schreiben der Beschwerdegegnerin vom 30. August 2013 geäussert hat. Die Beschwerdegegnerin hat schliesslich am 16. September 2013 zur Eingabe des Beschwerdeführers vom 7. September 2013 Stellung genommen. Weitere Eingaben seitens der Parteien sind nicht erfolgt. E. Die Beschwerde wurde an der Sitzung der II. zivilrechtlichen Abteilung des Bundesgerichts vom 14. November 2014 öffentlich beraten und das Urteil anschliessend an die Beratung und Abstimmung mündlich eröffnet. 